AGC041 B - Voting Judges (700)
最初の考察
問題を点数順にソートすればどの問題が採用されるかは二分探索できる
選んだ問題にM票入れて、残りはM票以下ずつを小さい方から選んだ問題の点数を超えないように入れる
点数を配分した後に選んだ問題がp番目以内になればOK
次の考察
上からp番目までは明らかに当選できる
二分探索時に上からp-1番目までには票を何票入れても問題ない
票を捨てられるのでこれらにM票ずつ入れる
あとは最初の考察どおり
一回の票のシミュレーションが$ O(N)
二分探索なのでシミュレーションする回数は$ O(\log N)
全体で$ O(N\log N)