本文共 1031 字，大约阅读时间需要 3 分钟。
很有趣的一道题吖！
做法：贪心+迭代
这种类型的贪心，和17EC-Final的那个最小化方差的题挺相似的。
#include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define rd(x) scanf("%d",&x)#define prt(x) printf("%d\n", x);#define prtvec(v) for(int i=0;i =x;i--)const int N=300000+10;const double EPS = 1e-8;int n;double f[N][102],g[N],p[N];int main(){ rd(n); rep(i,1,n) scanf("%lf",&p[i]), p[i]/=100.0; rep(i,1,n) f[n][i] = p[i]; rep(i,n+1,N-1) { double mx = 0; int bst = -1; rep(j,1,n) { double tmp = (1-f[i-1][j])*p[j]/f[i-1][j]; if (tmp > mx) { mx=tmp, bst = j; } } rep(j,1,n) f[i][j]=f[i-1][j]; f[i][bst]=(1-f[i-1][bst])*p[bst] + f[i-1][bst]; } double res = 0; rep(i,n,N-1) { g[i]=1; rep(j,1,n) g[i]*=f[i][j]; res=res+i*(g[i]-g[i-1]); } printf("%.5f\n", res);}
转载于:https://www.cnblogs.com/RUSH-D-CAT/p/8955538.html