読者です 読者をやめる 読者になる 読者になる

二分探索:平均の最大化(2題)

C++ 競技プログラミング

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
この本(通称:蟻本)の章末で紹介されている練習問題をひたすらといている。

二分探索。平均の最大化の問題である。
やっていることは最小値の最大化と同じ。二分探索は「何々の最大化」「何々の最小化」系の問題で、「何々」をソートできるときに使えるわけだな。

POJ2976: Dropping tests

2976 -- Dropping tests

問題概要

n 個のテストを受けた。それぞれのテストで b[i] 問中 a[i] 問正解した。テスト結果から k 個を取り除いて、平均を最大化したい。

解法

平均点を x 点以上にできるかどうかの判定が O(n log n) でできる。平均点の最大化を二分探索する。


POJ3111: K Best

http://poj.org/problem?id=:3111title

問題概要

蟻本 P.138 と同じ

解法

蟻本 P.138 と同じ