数学期望：小红拿宝箱

本文主要是介绍数学期望：小红拿宝箱，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://ac.nowcoder.com/acm/contest/80259/F

我们先从1--n每一个元素看，对于a[i]，可以后悔，这样相当于在n个元素中挑2个的期望，

为2*sum/n，假如没有后悔，剩下的期望就是(sum-a[i])/(n-1)了，此时我们还有一次反悔机会

我们不妨先排个序，假如我们选到了比期望大的数那么我们就直接选（否则下一次就是期望了），反之我们就返回使其值变成期望，于是答案就是(su[i]+(id-1)*k)（su[i]用后缀和维护），其中包含了原本去的a[i],我们把它减去即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n;
double su[100010];
bool cmp(double a,double b)
{return a<b;
}
double a[100010];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];if(n==1) cout<<a[1];if(n==1) return 0;sort(a+1,a+n+1,cmp);for(int i=n;i>=1;i--) su[i]=su[i+1]+a[i];//第一次就后悔double s=2*su[1]/n;//遍历1--n，每次取出一个取maxdouble ans=0;for(int i=1;i<=n;i++){double k=(su[1]-a[i])/(n-1);int id=lower_bound(a+1,a+n+1,k)-a;double tmp=su[id]+(id-1)*k;if(a[i]>=k) tmp-=a[i];else tmp-=k;tmp/=n-1;ans+=max(tmp+a[i],s);}printf("%.11lf",ans/n);
}

这篇关于数学期望：小红拿宝箱的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---