CF739E Gosha is hunting（wqs 二分）
panyf
·
·
题解
首先有一个 O(n^2\log n) 的做法，就是二分斜率 k，然后每用一个 A 类球答案就减 k，dp 求出 B 类球取 b 个的答案。正确性和实现可以参考其他题解。
考虑每个位置的四种选择：
-
用 A 和 B，答案加 p+u-pu-k
-
用 B，答案加 u-k
-
用 A，答案加 p
-
都不用，答案加 0。
考虑一个位置从不用 B 变成用 B，答案的增加量就是 x=\max(p+u-pu-k,p)-\max(u-k,0)，对 x 从大到小排序，取前 b 个即可。
可以分四种情况归并省掉排序，优化到 O(n\log n)。
```cpp
#include<bits/stdc++.h>
using namespace std;
enum{N=2009};
double ans,p[N],u[N];
int n,a,b;
struct T{
double x;
int a0,a1;
}t[N];
bool chk(double k){
int i,c=0;
ans=0;
for(i=1;i<=n;++i){
if(p[i]>p[i]+u[i]-p[i]*u[i]-k)t[i].a1=0,t[i].x=p[i];
else t[i].a1=1,t[i].x=p[i]+u[i]-p[i]*u[i]-k;
if(0>u[i]-k)t[i].a0=0;
else t[i].a0=1,t[i].x-=u[i]-k,ans+=u[i]-k;
}
sort(t+1,t+n+1,[](T a,T b){return a.x>b.x;});
for(i=1;i<=a;++i)c+=t[i].a1,ans+=t[i].x;
for(;i<=n;++i)c+=t[i].a0;
return c<b;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);
double l=0,r=1,m;
int i;
cin>>n>>a>>b;
for(i=1;i<=n;++i)cin>>p[i];
for(i=1;i<=n;++i)cin>>u[i];
for(i=1;i<77;++i){
m=(l+r)/2;
if(chk(m))r=m;else l=m;
}
cout<<fixed<<setprecision(9)<<ans+b*m;
}
```
暂时能过讨论区所有 hack 数据。