题面翻译

高橋君有 \(N\) 瓶糖水，青木君有 \(M\) 瓶糖水。

高橋君的第 \(i\) 瓶糖水有 \(A_i\) 份糖 \(B_i\) 份水。

青木君的第 \(i\) 瓶糖水有 \(C_i\) 份糖 \(D_i\) 份水。

将两人的糖水各选一瓶混合有 \(NM\) 种可能，求其中浓度第 \(k\) 大的糖水浓度是多少。

有 \(x\) 份糖和 \(y\) 份水的糖水浓度是 \(\dfrac{100x}{x+y}\%\)。

一个容易错误的贪心

一杯浓度大的糖水与另一杯糖水混合，另一杯糖水的浓度大不代表混合后的浓度大

如: \(7g\) 糖, \(14g\) 水为确定的一杯，称作 \(W\) 杯

然后还有两杯

\(A\) 杯为 \(7g\) 糖, \(4g\) 水, \(B\) 杯为 \(3g\) 糖, \(0g\) 水(浓度 \(100\)% ，大不大)

然后 \(W\) 与 \(A\) 混合后的浓度为 \(43.75\)%

\(W\) 与 \(B\) 混合后的浓度为 \(41.66666.....\)%

初始思路： 先想到二分浓度，然后想到 (假) 单调性，即前面提到的，然后枚举 \(n\) 杯糖水,与剩下 \(m\) 杯糖水混合是有(假的)单调性的，再进行二分看有多少混合后的糖水比当前 \(x\) 浓度大，不断二分，调了好久，最后终于发现了这贪心假了(估计是因为我太菜了)

下面放造的数据:

4 3 10
9 1
7 14
13 15
13 5
6 15
3 0
7 4

正确思路

\(1.\)依旧是二分浓度, 浓度设为\(x\)

\(2.\)计算有 \(res\) 杯(混合后的)浓度大于 \(x\)

\(3.\)(可以灵活变通),假设一杯糖水有 \(a\) g糖, \(b\) g水

在水不变的情况下若浓度为 \(x\) ，则应有 $ x\times\frac{b}{(1-x)} g$ 糖,

那么原来的糖水多余 \(s_x=\)(\(a- x\times\frac{b}{(1-x)}\))$ g$ (化简为\(\frac{a-(a+b)x}{1-x}\),然后高桥君和青木君的糖水都 \(\times (1-x)\)，不影响排序 ) 糖(可以是负数，表示缺少)

于是高桥君(\(s_x\))和青木君(\(s_y\))的每杯糖水都如此处理,满足\(s_x+s_y>0\) 的个数即为 \(res\) ，将其中一方取负就可以在另一方的糖水中二分查找（多余或缺少的糖）

正确代码：

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
const int N=5e4+5;
typedef long long ll;
int n,m;
ll k;
struct node{
	int sug,tot;
}a[N],b[N];
double c[N];

bool check(double w){//浓度 
	vector<double>vec;
	for(int i=1;i<=n;i++)
		vec.push_back(a[i].tot*w-a[i].sug);//取负 判断s[x]+s[y]正负 
	for(int i=1;i<=m;i++)
		c[i]=b[i].sug-b[i].tot*w;
	sort(c+1,c+m+1);
	ll res=0;

	for(int i=0;i<n;i++){
		int j=lower_bound(c+1,c+m+1,vec[i])-c;
		res+=(m-j+1);
	}
	if(res>=k)	return false;
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].sug>>a[i].tot;
		a[i].tot+=a[i].sug;//总质量 
	}
	for(int i=1;i<=m;i++){
		cin>>b[i].sug>>b[i].tot;
		b[i].tot+=b[i].sug;
	}
	
	double l=0,r=1;
	for(int iter=1;iter<=100;iter++){//二分浓度
		 if(check(mid))	r=mid;
		 else	l=mid;
	}
	cout<<fixed<<setprecision(12)<<l*100;
	return 0;
}