Room and Moor
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 842 Accepted Submission(s): 250Problem DescriptionPM 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:
InputThe 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.
OutputOutput the minimal f (A, B) when B is optimal and round it to 6 decimals.
Sample Input4 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
Sample Output1.428571 1.000000 0.000000 0.000000
Accepted Code:
1 /*************************************************************************
2 > File Name: 4923.cpp
3 > Author: Stomach_ache
4 > Mail: sudaweitong@gmail.com
5 > Created Time: 2014年08月08日 星期五 22时27分38秒
6 > Propose:
7 ************************************************************************/
8
9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17
18 const double eps = 1e-12;
19 const int maxn = 100002;
20 int n;
21 int a[maxn], st[maxn];
22
23 struct node {
24 double x; //区间均值
25 int l, r, one; //区间范围及1的个数
26 }A[maxn];
27
28 // unite i to j
29 void unite(int i, int j) {
30 A[j].l = A[i].l;
31 A[j].x = A[j].one + A[i].one + 0.0;
32 A[j].x /= A[j].r - A[j].l + 1;
33 A[j].one = A[i].one + A[j].one;
34 }
35
36 double solve() {
37 int len = 1;
38 for (int i = 1; i <= n; i++) {
39 A[len].x = a[i] + 0.0;
40 A[len].l = i;
41 i++;
42 while (i <= n && a[i] == a[i-1]) i++;
43 A[len].r = i - 1;
44 i--;
45 if (a[i]) A[len].one = A[len].r - A[len].l + 1;
46 else A[len].one = 0;
47 len++;
48 }
49 int top = 0;
50 for (int i = 1; i < len; i++) {
51 while (top && A[i].x < A[st[top-1]].x) {
52 unite(st[top-1], i);
53 top--;
54 }
55 st[top++] = i;
56 }
57 double ans = 0.0;
58 for (int i = 0; i < top; i++) {
59 for (int j = A[st[i]].l; j <= A[st[i]].r; j++) {
60 ans += (a[j] - A[st[i]].x) * (a[j] - A[st[i]].x);
61 }
62 }
63 return ans + eps;
64 }
65
66 int main(void) {
67 int t;
68 scanf("%d", &t);
69 while (t--) {
70 scanf("%d", &n);
71 for (int i = 1; i <= n; i++) scanf("%d", a + i);
72 printf("%.6f\n", solve());
73 }
74 return 0;
75 }
原文：http://www.cnblogs.com/Stomach-ache/p/3900911.html