Room and Moor

11916: Room and Moor

时间限制: 6 Sec  内存限制: 256 MB
提交: 2  解决: 2
[提交] [状态] [命题人:外部导入]

题目描述

PM Room defines a sequence A = {A1, A2,..., AN}, each of which is either 0 or 1. In order to beat him, programmer Moor has to construct another sequence B = {B1, B2,... , BN} of the same length, which satisfies that:

 

输入

The input consists of multiple test cases. The number of test cases T(T<=100) occurs in the first line of input.

For each test case:
The first line contains a single integer N (1<=N<=100000), which denotes the length of A and B.
The second line consists of N integers, where the ith denotes Ai.

 

输出

Output the minimal f (A, B) when B is optimal and round it to 6 decimals.

 

样例输入

复制样例数据

4
9
1 1 1 1 1 0 0 1 1
9
1 1 0 0 1 1 1 1 1
4
0 0 1 1
4
0 1 1 1

样例输出

1.428571
1.000000
0.000000
0.000000

 

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
const ll mod = 1e9 + 7;
const double eps = 1e-7;
struct node {int cnt0, cnt1;double val;
} v[maxn];
int T, n, cnt;
int c[maxn];int main() {//freopen("1.txt", "r", stdin);stack<node> sk;scanf("%d", &T);while (T--) {scanf("%d", &n);for (register int i = 1; i <= n; ++i)scanf("%d", c + i);int l = 1, r = n;while (c[l] == 0 && l <= n)l++;while (c[r] == 1 && r >= 1)r--;if (l > r) {printf("0.000000\n");continue;}cnt = 0;for (register int i = l; i <= r;) {int n0 = 0, n1 = 0;while (c[i] == 1 && i <= r)i++, n1++;while (c[i] == 0 && i <= r)i++, n0++;v[++cnt].cnt0 = n0;v[cnt].cnt1 = n1;v[cnt].val = 1.0 * n1 / (double) (n0 + n1);//sk.push(v[cnt]);
        }//while (!sk.empty())sk.pop();for (register int i = 1; i <= cnt; ++i) {if (sk.empty())sk.push(v[i]);else {node last = sk.top();if (last.val <= v[i].val) {sk.push(v[i]);} else {node cur = v[i];while (true) {last = sk.top();if (cur.val < last.val) {cur.cnt0 += last.cnt0;cur.cnt1 += last.cnt1;cur.val = 1.0 * cur.cnt1 / (double) (cur.cnt0 + cur.cnt1);sk.pop();} else {sk.push(cur);break;}if (sk.empty()) {sk.push(cur);break;}}}}}node o;double res = 0;while (!sk.empty()) {o = sk.top();//cout<<"debug o.val="<<o.val<<' '<<"debug o.cnt0="<<o.cnt0<<' '<<"debug o.cnt1="<<o.cnt1<<endl;
            sk.pop();res += o.val * o.val * o.cnt0 + (1.0 - o.val) * (1.0 - o.val) * o.cnt1;}printf("%.6f\n", res);}return 0;
}