とても典型的な「平均値の最大化」→「二分探索」の問題！

問題へのリンク

問題概要

$N$ 個の食塩水がある。 $i$ 番目の食塩水は、重さが $w_{i}$ グラムであり、濃度 $p_{i}$ パーセントである。

これらの食塩水から $K$ 個選んで混ぜてできる食塩水の濃度の最大値を求めよ。

制約

$1 \le K \le N \le 1000$

考えたこと

ザ・「平均値の最大化」問題である。この手の問題は二分探索が効く！

混ぜてできる食塩水の濃度を $x$ パーセント以上にできるかどうかを判定する問題を解こう。

さて、混ぜる $K$ 個の各食塩水について、溶けている食塩の重さを $s_{1}, s_{2}, \dots, s_{K}$ として、食塩水の重さを $t_{1}, t_{2}, \dots, t_{K}$ としたとき、混ぜた食塩水が $x$ パーセント以上である条件を考察すると、

$\displaystyle \frac{s_{1} + s_{2} + \dots + s_{K}}{t_{1} + t_{2} + \dots + t_{K}} \ge \frac{x}{100}$
⇔ $\displaystyle (s_{1} - \frac{t_{1}}{100} x) + (s_{2} - \frac{t_{2}}{100} x) + \dots + (s_{K} - \frac{t_{K}}{100} x) \ge 0$

となる。よって、 $s_{i} - \frac{t_{i}}{100} x$ の総和によって判定できることがわかった。判定問題は次のようにして解決できる。

$N$ 個の食塩水のうち、

$\displaystyle (食塩の量) - \frac{(食塩水の量)}{100} x$

の値が大きい順に $K$ 個とった総和が 0 以上であるかを判定する

計算量は、二分探索のイテレーション回数を $X$ として、 $O(X N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<double> w(N), p(N);
    for (int i = 0; i < N; ++i) cin >> w[i] >> p[i];
    
    double lo = 0.0, hi = 100.0;
    for (int i = 0; i < 50; ++i) {
        double mi = (lo + hi) / 2;
        vector<double> tmp(N);
        for (int j = 0; j < N; ++j) {
            tmp[j] = (p[j] - mi) * w[j];
        }
        sort(tmp.begin(), tmp.end(), greater<double>());
        double sum = 0.0;
        for (int j = 0; j < K; ++j) sum += tmp[j];
        if (sum < 0.0) hi = mi;
        else lo = mi;
    }
    cout << fixed << setprecision(9) << hi << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 034 D - 食塩水 (試験管水色)

問題概要

制約

考えたこと

コード