キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) D - Project Planning (400)
コンテスト中の考察
昇順にソートすると右からk-1個だけでは作れない
小さい方$ n-k+1個の優先度付きキューと大きい方$ k-1個の優先度付きキューを用意する
小さい方のキューの最大値だけペアを作る
小さい方のキューの最大値と大きい方の全部でペアを作る
今まで作った数は変数に記憶しておく
大きい方のキューで作った数の合計以下の物を取り除く
大きい方のキューのサイズが小さくなったら$ k-1になるまで小さい方のキューのから持ってくる
大きい方のキューに持ってくるときは今まで作った数の分下駄を履かせる
大きい方の最小値が小さい方の最大値より小さいなら交換する
公開されたテストケースを見た結果、正答より小さい値を答えていた
解説の解法
計何個作れるかを二分探索する
累計$ m個作れるとした場合、$ A_i = \min(A_i,m)として良い
同じのを同時に2個以上使えないため
$ \sum_i A_i \ge kmになればm個作ることができる