Boxes

題意：

有n個(gè)盒子，每個(gè)盒子里要么是黑球，要么是白球，你可以花C的代碼得知剩下所有盒子中黑球數(shù)量和白球數(shù)量，(只是知道總數(shù)量，并不知道具體哪個(gè)盒子里是什么)，你可以可以花費(fèi)wi的代價(jià)開第i個(gè)箱子。問想知道所有盒子里球的情況，花費(fèi)的最少期望是多少？

題解：

首先這個(gè)C最多只用花一次，且第一次花，因?yàn)槟愕谝淮位ㄍ曛?#xff0c;就知道黑白所有的數(shù)量，如果你開了箱子，剩下的箱子反推就知道，所以這個(gè)C只用花一次。
如果只花一次C，那我們就要考慮剩下的箱子打開情況，按照wi升序排列，我們肯定優(yōu)先打開花費(fèi)小的箱子，一直開，直到開到一個(gè)后綴全是同色的位置。這樣的代價(jià)：$C+\sum wi(1?1/(2^{n?i}))$
公式得到過程：
如果我們當(dāng)前打算開第i個(gè)，那么就還有n-i個(gè)沒開，如果不繼續(xù)開箱子，說明后面都是同色的，后面同色的概率是$1/2^{n?i}$,如果第i個(gè)箱子開，就說明后面不都是同色的，概率就是$1?1/2^{n?i}$,期望就再乘上wi
當(dāng)然，可以不整那么多虛的，有可能直接打開所有盒子的總花費(fèi)更優(yōu)，此時(shí)打開所有盒子的概率都是1，總期望就是${\sum }_{i=1}^{n}wi$
兩個(gè)情況取最小

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt","r",stdin);#endif } const int maxn=1e5+9; long double a[maxn]; long double sum[maxn]; long double poww(long double a,ll b){long double ans=1;while(b){if(b&1)ans*=a;a*=a;b>>=1; }return ans; } int main() {//rd_txt();int n;double c;cin>>n>>c;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];long double ans=c;long double t=1.0;for(int i=1;i<=n;i++){ans+=a[i]*(1.0-1.0/poww(2,n-i));}ans=min(ans,sum[n]);printf("%.8Lf\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Boxes的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。