ABC236E 解法 平均値,中央値共に binary search で求まる. 値 \(x\) を固定した場合,平均が \(x\) 以上になる事は \[\sum_{i \in I} a_{i} / \sum_{i \in I} 1 \geq x\] と表せる.すなわち, \[\sum_{i \in I} (a_{i} - x) \geq 0\] と同値.これは先頭から見た DP で計算可能. 値 \(x\) を固定した場合,中央値が \(x\) 以上になることは, \(x\) 以上の個数が半分以上になれば良い. つまり,\(x\) 以上と \(x\) 未満の \(2\)値に帰着できる. \(…