ARC 101-200/ARC197B - Greater Than Average - 競技プログラミング用 知識集積所

---

問題

ARC197B

必要知識

簡単な内容は省略

• 貪欲法（アルゴリズム系）（未作成）
• 全探索（未作成）
• 尺取法または二分探索（未作成）

考え方

平均以上がm個、という部分列があるかどうかの判断方法を考える。

ソートしてあるとして考える。
平均以上のm個を、不連続に採用するメリットはない。
なぜなら、i番目とi+2番目が採用されてi+1番目が採用されない解が条件を満たすなら、
i番目とi+1番目が採用されてi+2番目が採用されない解も必ず条件を満たすからである。
したがって、これらm個は連続して採用すると考えてよい。

さらに、平均以下の数は、採用しないメリットがない。
平均以上がm個ある部分列に平均以下の値を1つ加えると、平均値が下がるだけなので、加えた後の部分列も平均以上がm個以上あるからである。

したがって、小さい方からいくつかを選んだ部分列の中での最大値のみ考えればよい。
採用する個数の全探索ループの中で、平均値より大きい数の個数を尺取法または二分探索で求めていけばよい。

解答例

解答例

注意点

平均値との大小判定に注意。

平均値を整数で出すと、平均値との大小関係でおかしな関係が発生する可能性がある。
かといって、double型で出すのは精密な比較に不安が残る。
平均値との大小ではなく、その値×個数が合計値より大きいかで判定する方が確実。
その場合、long long型を用いること。

別解