[ABC294F] Sugar Water 2
kelanjie
·
·
题解
一个容易错误的贪心(仅用于警示)
一杯浓度大的糖水与另一杯糖水混合，另一杯糖水的浓度大不代表混合后的浓度大
如: 7g 糖, 14g 水为确定的一杯，称作 W 杯
然后还有两杯
然后 $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
在水不变的情况下若浓度为 $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$ ，将其中一方取负就可以在另一方的糖水中二分查找（多余或缺少的糖）
## 正确代码：
```cpp
#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;
}
```