神秘题目，本人用的贪心做的，发现一个二分写法，故记录一下。
题意
有 \(2N\) 个灯泡，分为 \(A\) 组和 \(B\) 组各 \(N\) 个。
你可以从中选取任意个灯泡，每选取一个灯泡需要花费 1 的代价。
在你选取完之后，系统会随机在A类和B类中选择一个类型，并点亮那一类的所有灯泡。你选取的每个点亮的灯泡会给你带来等于它权值的收益。
现在请你合理选取灯泡，以最大化可能的最小收益。你只需要求出来这个收益即可。
做法
最大值最小，并且这个问题是具有单调性的，一个值如果是合法的，那么比它小的都是可以凑出来的。
显然最佳的是从大往小选择，我们将 A,B 从大到小排序跑前缀和。
check 枚举使用了几个，在 suma,sumb 中二分至少使用几个才能凑出来这么多。
也就是找出来 mid+i 就行。
代码↓
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
const double eps=1e-6;
int n;
double a[MN], b[MN], suma[MN], sumb[MN];
bool check(double mid){for(int i=1; i<=n+n; ++i){int posa=lower_bound(suma+1,suma+n+1,mid+i)-suma;int posb=lower_bound(sumb+1,sumb+n+1,mid+i)-sumb;if(posa>n||posb>n) return false;if(posa+posb<=i) return true;}return false;
}
bool cmp(double a, double b){return a>b;
}
void Solve(){cin>>n;for(int i=1; i<=n; ++i) cin>>a[i]>>b[i];sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp);for(int i=1; i<=n; ++i){suma[i]=suma[i-1]+a[i];sumb[i]=sumb[i-1]+b[i];}double l=0, r=1e9, res=0;while(r-l>eps){double mid=(l+r)/2;if(check(mid)){l=mid; res=mid;}else r=mid;}cout<<fixed<<setprecision(4)<<res<<'\n';return;
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);Solve(); return 0;
}