1. 首页
2. 其他
3. 本页

HDU 5753 Permutation Bo (规律)

题目链接：点我~~

题意：~~

思路：根据期望的线性性，我们可以分开考虑每个位置对答案的贡献。

可以发现当i不在两边的时候和两端有六种大小关系，其中有两种是对答案有贡献的。

那么对答案的贡献就是ci/3。

在两端的话有两种大小关系，其中有一种对答案有贡献。

那么对答案的贡献就是ci/2。

复杂度是O(n)。

注意特判n=1的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define mp make_pair
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

double a[1100];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%lf",&a[i]);
        }
        if(n==1) printf("%.6lf\n",a[1]);
        else
        {
            double sum=(a[1]+a[n])*3;
            for(int i=2; i<=n-1; i++)
            {
                sum+=a[i]*2;
            }
            printf("%.6lf\n",sum/6);
        }
    }
    return 0;
}