AtCoder Beginner Contest 034 D - 食塩水
解法
ヒントに書いてあるとおり, 食塩水の濃度 x について二分探索します。
濃度が x 以上になるかどうかは以下のようにしてわかります。
食塩水全体の質量を S, 食塩の量を T とすると, 条件は T/S >= x i.e. T - x*S >= 0 となります。これを達成するための作戦は, 各食塩水に対して, (食塩の質量) - x*(食塩水の質量) が大きい順に食塩水を選んでいくのが最適です。大きい物 K 個を選んだ時に, T-x*S >= 0 となるかどうかで判定しましょう。
const int MAXN = 1010; int w[MAXN], p[MAXN]; int N, K; bool ok(double x) { vector<double> v(N); for (int i = 0; i < N; i++) { double tmp = w[i] * (p[i]/100.); v[i] = tmp-x*w[i]; } sort(v.rbegin(), v.rend()); double sum = 0; for (int i = 0; i < K; i++) sum += v[i]; return sum >= 0; } int main() { cin >> N >> K; for (int i = 0; i < N; i++) cin >> w[i] >> p[i]; double low = 0, high = 1; for (int i = 0; i < 100; i++) { const double med = (high+low)/2; if (ok(med)) low = med; else high = med; } printf("%.10lf\n", low*100); return 0; }