WC模拟（1.12） T1 小C饮水记

本文主要是介绍WC模拟（1.12） T1 小C饮水记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小C饮水记

题目背景：

1.12 WC模拟T1

分析：暴力 + 链表

 

首先可以比较轻松的发现，对于一个区间，肯定是从区间最小一直操作到区间最大，那么对于第i大的数，贡献为x / 2ⁱ，那么我们将对于区间的考虑，转化为对于每一个数的贡献考虑，问题可以转化为，我们从当前数字往前扫，每到一个比它大的数，当前位置的贡献为上一个位置的1 / 2，否则为上一个位置的贡献，这样，统计左右两边的权值之和再相乘最后除以二得到y,那么这个数的贡献就是x * y，然后我们又发现，这个题的精度要求是非常小的，这就意味着，我们不用找到所有比它大的数，只需要找一定个数的就可以了，我们可以从小到大枚举数字，每次想左右各找t个，然后删掉当前这个数，可以用双向链表很简单的维护。复杂度O(nt + nlogn)，t大概取35 ~ 45就可以了。

 

Source:

/*created by scarlyw
*/
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>
#include <ctime>
#include <bitset>///*
template<class T>
inline void R(T &x) {static char c;static bool iosig;for (c = getchar(), iosig = false; !isdigit(c); c = getchar())	if (c == '-') iosig = true;	for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');if (iosig) x = -x;
}
//*/const int MAXN = 1000000 + 10;
const int MAX = 35;int n;
int a[MAXN];
struct data {int num, ori;inline bool operator < (const data &a) const {return (num == a.num) ? (ori < a.ori) : (num < a.num);}
} c[MAXN];struct list {int pre, suc;
} l[MAXN];inline void read_in() {R(n);for (int i = 1; i <= n; ++i) R(a[i]), c[i].num = a[i], c[i].ori = i;std::sort(c + 1, c + n + 1);for (int i = 1; i <= n; ++i) l[i].pre = i - 1, l[i].suc = i + 1;
}inline void solve() {int rk, last, cnt, cur;double ret, f_ans, b_ans, ans = 0;for (int i = 1; i <= n; ++i) {cur = c[i].ori;last = cur, ret = 1, f_ans = 0, cnt = 0;while (cnt <= MAX && last != 0) {rk = l[last].pre, f_ans += (double)(last - rk) * ret;ret /= 2.0, cnt++, last = rk;}last = cur, ret = 1, b_ans = 0, cnt = 0;while (cnt <= MAX && last != n + 1) {rk = l[last].suc, b_ans += (double)(rk - last) * ret;ret /= 2.0, cnt++, last = rk;}ans += b_ans * f_ans * (double)c[i].num / 2.0;l[l[cur].pre].suc = l[cur].suc, l[l[cur].suc].pre = l[cur].pre;}printf("%0.9lf", ans / (double)n / (double)n);
}int main() {freopen("drink.in", "r", stdin);freopen("drink.out", "w", stdout);read_in();solve();return 0;
}

这篇关于WC模拟（1.12） T1 小C饮水记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---