はまやんはまやんはまやん

hamayanhamayan's blog

C. Sagheer and Nubian Market [Codeforces Round #417 (Div. 2)]

http://codeforces.com/contest/812/problem/C

問題概要

N個の商品がある。
ここから、K個の商品をS円以内で買うとする。
K個の商品を買ったとき、i番目の商品の値段はA[i] + K*i(iは1-indexed)となる。
この時、Kを最大化して、その中で合計金額Tを最小化せよ。

解説

http://codeforces.com/contest/812/submission/27515355
二分探索で解く。

まず、Kが増加するにつれて、合計金額Tは単調増加する。
その為、Kについて二分探索することで、答えが導ける。

summing(int K)を作るが、貪欲に選んでいけば良い。
具体的には、Kが分かっているので、A[i] + K*iを使って各商品の値段が決定する。
後は、これを昇順ソートして、先頭のK個を選択すれば、それが最小の合計金額となる。