mayoko’s diary

プロコンとかいろいろ。

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;
}