blue_jam https://blog.hatena.ne.jp/blue_jam/ blue_jamの日記 https://blue-jam.hatenablog.com/ 競技プログラミング 概要 コストa[i]と評価値s[i]の組の列がある． この中から，N（奇数）個の要素をコストの合計がFを超えないように選び，メディアンを最大化したい． 解法 メディアンはソートしたときの中央値であり，中央の値以外には影響をうけないことを利用する． N = 2K + 1とする． コストについてソート． あるインデックスiについて，iより小さいインデックスの中からK個選ぶときのコストの最小値を計算．iより大きいインデックスについても同様に計算．この計算は，PriorityQueueを用いることでO(N log N)時間で事前に計算できる． 上記二つの値の合計とi番目のコストの合計がF以下であれば，… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblue-jam.hatenablog.com%2Fentry%2F2014%2F08%2F08%2F232903" title="POJ 2010: Moo University - Financial Aid - blue_jamの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-08-08 23:29:03 rich https://blue-jam.hatenablog.com/entry/2014/08/08/232903 1.0 100%