有大佬能解释一下 周赛F 小红拿宝箱的代码吗
有大佬能解释一下最后一题的代码吗
小红击杀了若干只怪物后,爆出了若干个宝箱。她准备取出一些宝箱的金币,但是,当小红取到了2个宝箱的金币后,其余宝箱就会消失。现在小红每次可以随机打开一个宝箱查看内部的金币,然后小红可以选择拿或者不拿。但是,小红一共只有最多一次“不拿”的机会。当小红选择“不拿”以后,该宝箱会混入所有未抽取的宝箱。如果小红选择了“拿”,则获得该宝箱的金币,同时该宝箱消失。现在小红想知道,自己若采用最优策略(即最大化最终获取金币的期望),可以得到金币数量的期望是多少?请注意,小红在开箱之前,已经通过大预言术得知了每个箱子中的金币数量。只是由于箱子被打乱了,小红在打开之前,不知道具体那一个箱子有多少金币。
#include<bits/stdc++.h>
usingnamespacestd;
typedeflonglongll;
#define N 1000000
inti,j,k,n,m,t;
doublef[N+50],res,tot,tot2,g[N+50];
intmain(){
//ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(i=1;i<=n;i++){
cin>>f[i]; tot+=f[i]; tot2+=f[i];
}
if(n<=2){
printf("%.20lf",tot); return0;
}
sort(f+1,f+n+1);
j=0;
for(i=n;i>=1;i--){
while(j<n&&f[j+1]<=(tot-f[i])/(n-1)){
j++; tot2-=f[j];
}
doublet1;
t1=tot2+j*(tot-f[i])/(n-1);
if(i<=j)t1-=(tot-f[i])/(n-1);
elset1-=f[i];
res+=max(tot/n*2,f[i]+t1/(n-1));
}
printf("%.20lf",res/n);
}