ABC294F Sugar Water 2

题目链接

分析

$\frac{100x}{x+y}$是糖的浓度的百分比值，讨论时只考虑$\frac{x}{x+y}$即可，后面再去乘100，待求解的问题本质上就是求$NM$个组合的浓度中第K大。

直接二分最终的浓度，找到最小的浓度，满足“刚好有K个大于等于该浓度的组合”。

对于一个二分到的浓度$T$，Takahashi的第$i$杯糖水中有$S_i$克糖和$W_i$克水，如果只要求浓度为$T$，那么他还富余了$(S_i-\frac{T}{1-T}\times W_i)$克糖（推理过程如下），富余的糖就可以给Aoki的糖水使用。
$$
设有W_i克水，需要x克糖才能使得糖水的浓度为T，则有\
T=\frac{x}{x+W_i}\rightarrow \frac{1}{T}=1+\frac{W_i}{x}\rightarrow x=W_i \frac{T}{1-T}\
很容易即可推出出Takahashi盈余的糖分为\
S_i-W_i \frac{T}{1-T}
$$
如此，我们得到了一个在$O(nlog\ n)$时间复杂度内计算有多少个大于等于浓度T的组合的方法：

vector<double> eSuger(N);
double tmp = T / (1 - T);
// 对于二分到的浓度T，计算将Takahashi的每杯糖水盈余的糖分，保存到vector中
for (int i = 0; i < N; i++) {
    eSuger[i] = (double) Ta[i].suger - tmp * Ta[i].water;
}
// 从小到大排序，方便后面用lower_bound函数
sort(eSuger.begin(), eSuger.end());
LL cnt = 0;
// 枚举Aoki的每杯糖水
for (int i = 0; i < M; i++) {
    // 计算这杯糖水需要多少糖分才能使其浓度为T
    double nSuger = tmp * Ao[i].water - Ao[i].suger;
    // Takahashi有多少杯糖水可以满足Aoki的这杯糖水所需的糖分
	// 把所有的糖水加起来就是满足“浓度大于等于T”的组合数
    cnt += N-(lower_bound(eSuger.begin(),eSuger.end(),nSuger)-eSuger.begin());
}

代码

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

struct juice {
    int suger, water;

    juice(int s = 0, int w = 0) : suger(s), water(w) {}
};
int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int N, M;
    LL K;
    cin >> N >> M >> K;

    int a, b;
    vector<juice> Ta, Ao;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        Ta.push_back(juice(a, b));
    }
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        Ao.push_back(juice(a, b));
    }

    double l = 0, r = 1;
    int t = 100;
    vector<double> eSuger(N);
    while (t--) {
        double C = (l + r) / 2;
        double tmp = C / (1 - C);
        for (int i = 0; i < N; i++) {
            eSuger[i] = (double) Ta[i].suger - tmp * Ta[i].water;
        }
        sort(eSuger.begin(), eSuger.end());
        LL cnt = 0;
        for (int i = 0; i < M; i++) {
            double nSuger = tmp * Ao[i].water - Ao[i].suger;
            cnt += N - (lower_bound(eSuger.begin(), eSuger.end(), nSuger) - eSuger.begin());
        }
        
		// 看题解学到的新写法
        (cnt < K ? r : l) = C;
    }
    cout << fixed << setprecision(16) << l * 100 << endl;

    return 0;
}