【Tyvj2046】掷骰子

好水一道题

掷骰子
Description

      Rainbow和Freda通过一次偶然的机会来到了魔界。魔界的大门上赫然写着:
小盆友们,欢迎来到魔界~!乃们需要解决这样一个问题才能进入哦lala~
有N枚骰子,其中第i(1<=i<=N)枚骰子有a[i]面。掷出第i枚骰子时,这a[i]面中只有一面朝上,而且这a[i]面每面朝上的概率都相等,为1/a[i].
门上还写道:这N个骰子,显然一共有M=Sigma(a[i])个面。你们要做的就是把1~M这M个数字不重不漏地写到这M个面上。同时掷出这N个骰子,你们的得分就是这N个骰子朝上的面上的数字之和。你们要做的,就是使你们的得分的期望值最大哦~

Input Format
    第一行一个整数N,表示骰子的数目。
    第二行N个整数,第i个整数a[i]表示第i个骰子有多少个面。

Output Format
    一行一个实数Ans,表示Freda和Rainbow得分的最大期望值,保留三位小数。
Sample Input
   2
   1 4

Sample Output
    7.500

Hint
样例解释
   在第一个骰子的唯一一面写上5,第二个骰子的四面分别写上1,2,3,4。这样得分的期望就是5/1+(1+2+3+4)/4=7.5了。
数据范围与约定
   对于30%的数据,N<=10
   对于50%的数据,N<=1000.
   对于100%的数据,0 < N <= 50000, 0 < a[i] <= 100.

题解:

贪心思想,面少的放大数,加上等差数列求值

证明:蒟蒻我不会证

废话少说,上代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[50010];
double s[5001000];
int main(){
    freopen("dice.in","r",stdin);
    freopen("dice.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        m+=a[i];
    }
    for(int i=1;i<=m;i++) s[i]=s[i-1]+i;
    sort(a+1,a+n+1);
    double ans=0.0;
    int last=m;
    for(int i=1;i<=n;i++){
        ans+=(double)((s[last]-s[last-a[i]])/(double)a[i]);
        last-=a[i];
    }
    printf("%.3lf",ans);
    return 0;
}

 

上一篇:asp.net core系列 66 Dapper介绍--Micro-ORM


下一篇:asp.net core系列 66 Dapper介绍--Micro-ORM