[CEOI 2017] Sure Bet
神秘題目，本人用的貪心做的，發現一個二分寫法，故記錄一下。
題意
有 \(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;
}
浙公網安備 33010602011771號