题面

题解

有精度要求所以只用求几十次就差不多了

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 300005;

struct node {

	int v, id;

	inline bool operator <(const node &o)const {

		return v < o.v || (v == o.v && id < o.id);

	}

}p[MAXN];

int n, pre[MAXN], nxt[MAXN];

int main () {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i)

		scanf("%d", &p[i].v), p[i].id = i, pre[i] = i-1, nxt[i] = i+1;

	sort(p + 1, p + n + 1);

	double ans = 0;

	for(int i = 1; i <= n; ++i) {

		double l = 0, r = 0, pw = 1;

		int x = p[i].id, lp = x, rp = x;

		for(int j = 1; j <= 50; ++j) {

			pw /= 2;

			if(lp) l += pw*(lp - pre[lp]), lp = pre[lp];

			if(rp<=n) r += pw*(nxt[rp] - rp), rp = nxt[rp];

		}

		ans += 2*l*r*p[i].v;

		nxt[pre[x]] = nxt[x];

		pre[nxt[x]] = pre[x];

	}

	printf("%.15f\n", ans/n/n);

}

巴特西

Codeforces 380E Sereja and Dividing

题面

题解

CODE

最新文章

热门文章