hdu4923

Room and Moor

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 557 Accepted Submission(s): 159

Problem Description

PM Room defines a sequence A = {A₁, A₂,..., A_N}, each of which is either 0 or 1. In order to beat him, programmer Moor has to construct another sequence B = {B₁, B₂,... , B_N} of the same length, which satisfies that:

Input

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 A_i.

Output

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

Sample Input

1 1 1 1 1 0 0 1 1

1 1 0 0 1 1 1 1 1

0 0 1 1

0 1 1 1

Sample Output

1.428571

1.000000

0.000000

思路：首先去掉前导零和最后的1，相当于把整个序列分成几个区间，每部分以1开头，0结尾，即如1 0 1 1 0 0等，可知对于每一个区间，要取得最小值，那这个部分所有的值即对应的这个区间内的平均数，如果这个平均数和前面一个区间的相比较大，就压入栈，否则将栈里的元素顶出，并与当前区间合并求平均数……知道比前面的大为止，最后求出每个区间的对应的Seg(ai - bi)^2 就可以了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <stack>
 4 #define eps 0.00000001
 5 using namespace std;
 6 
 7 const int LEN = 100010;
 8 int arr[LEN];
 9 struct line
10 {
11     int l, r, sum;
12     double rate;
13 };
14 stack<line> s;
15 int main()
16 {
17     int T, n;
18     line tmp;
19     scanf("%d", &T);
20     while(T--)
21     {
22         scanf("%d", &n);
23         for(int i = 0; i < n; i++)
24             scanf("%d", &arr[i]);
25         int h = 0;
26         while(arr[h] == 0)
27             h++;
28         int k = n - 1;
29         while(arr[k] == 1)
30             k--;
31         for(int i = h; i <= k; i++)
32         {
33             if (i == h || i > h && arr[i-1] == 0 && arr[i] == 1)
34             {
35                 tmp.l = i;
36                 tmp.sum = 0;
37             }
38             if (i < k && arr[i] == 0 && arr[i+1] == 1 || i == k)
39             {
40                 tmp.r = i;
41                 tmp.rate = tmp.sum * 1.0 / ((tmp.r - tmp.l + 1) * 1.0);
42                 while(true)
43                 {
44                     if (s.empty() || s.top().rate - tmp.rate < eps)
45                     {
46                         s.push(tmp);
47                         break;
48                     }
49                     if (s.top().rate - tmp.rate > eps)
50                     {
51                         tmp.l = s.top().l;
52                         tmp.sum += s.top().sum;
53                         tmp.rate = tmp.sum*1.0 / ((tmp.r - tmp.l + 1)*1.0);
54                         s.pop();
55                     }
56                 }
57             }
58             if (arr[i] == 1)
59                 tmp.sum++;
60         }
61         double ans = 0;
62         while(!s.empty())
63         {
64             ans += ((1 - s.top().rate) * (1 - s.top().rate) * s.top().sum + s.top().rate * s.top().rate * (s.top().r - s.top().l + 1 - s.top().sum));
65             s.pop();
66         }
67         printf("%f
", ans);
68     }
69     return 0;
70 }

View Code