hdu 4923 Room and Moor [ 找规律 + 单调栈 ]

Room and Moor

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

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

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

Sample Output

1.428571 1.000000 0.000000 0.000000

Author

BUPT

Source

2014 Multi-University Training Contest 6

Recommend

We have carefully selected several similar problems for you: 5189 5184 5181 5180 5177

又一道G++ T，C++ AC 的好题！！！！

题意及题解转自：

http://blog.csdn.net/a601025382s/article/details/38423069

题意：

给定一个长度为n的，由0和1组成的序列ai，求一个序列bi，使得∑(bi-ai)^2最小。其中0<=bi<=1,bi<=b(i+1)，bi为浮点型。输出最小的∑(bi-ai)^2的值。

题解：

对于ai序列中，开头的连续0,和结尾的连续1可以省略，因为bi中必定可以赋值连续0和连续1相同的值，使得(bi-ai)^2=0；

对于剩余的序列，我们可以分组，每组为连续1+连续0的形式（例如110010可以分成1100和10）。

对于每个组中的数ai，他们对应的bi必定是相同的。证：假设0对应的bi确定，那么要使∑(bi-ai)^2最小，1对应的bi肯定等于0对应bi中的最小值；同理1对应的bi确定时也一样。之后我们可以发现，这个值正好是rate=num1/(num1+num0)，numi表示i的个数。

之后我们遍历每个分组，将每个组压入栈中。在压入栈之前，我们需要判断rate是否呈递增的，若是呈递增的，那么直接要入栈中，因为我们可以两个分组取不同的rate；若不是呈递增，那么我们需要将最后一个组出栈，然后合并，因为我们要保证bi的呈递增的；然后判断这个新的组入栈是否能是栈呈递增，不能则重复前面的动作，直到呈递增或者栈为空为止，之后将新的组压入栈中。

最后得到一个递增的栈，我们直到了每个分组的rate值，那么就能求∑(bi-ai)^2了。

13197281	2015-03-21 16:21:03	Accepted	4923	1638MS	2408K	2440 B	C++	czy
13197275	2015-03-21 16:20:38	Time Limit Exceeded	4923	6000MS	2468K	2440 B	G++	czy

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <stack>
  4 #include <vector>
  5 #include <algorithm>
  6 
  7 #define ll long long
  8 int const N = 100005;
  9 int const M = 205;
 10 int const inf = 1000000000;
 11 ll const mod = 1000000007;
 12 
 13 using namespace std;
 14 
 15 int n;
 16 double ans;
 17 int aa[N];
 18 int a[N];
 19 int tot;
 20 ll qcnt1[N];
 21 ll qcnt[N];
 22 int T;
 23 
 24 void ini()
 25 {
 26     ans=0;
 27     tot=0;
 28     int i,j;
 29     int st,en;
 30     scanf("%d",&n);
 31     for(i=1;i<=n;i++){
 32         scanf("%d",&aa[i]);
 33     }
 34     st=1;
 35     while(st<=n){
 36         if(aa[st]==0){
 37             st++;
 38         }
 39         else{
 40             break;
 41         }
 42     }
 43     if(st==n+1) return;
 44     en=n;
 45     while(en>st){
 46         if(aa[en]==1){
 47             en--;
 48         }
 49         else{
 50             break;
 51         }
 52     }
 53     j=0;
 54     for(i=st;i<=en;i++){
 55         j++;
 56         a[j]=aa[i];
 57     }
 58     tot=j;
 59     //printf(" tot=%d
",tot);
 60 }
 61 
 62 void solve()
 63 {
 64     int r;
 65     r=0;
 66     ll cnt1,cnt0;
 67     ll cnt;
 68     int i;
 69     int now=1;
 70     cnt1=cnt0=0;
 71     for(i=1;i<=tot;i++){
 72         if(now==1){
 73             if(a[i]==1){
 74                 cnt1++;
 75             }
 76             else{
 77                 cnt0++;
 78                 now=0;
 79             }
 80         }
 81         else{
 82             if(a[i]==0){
 83                 cnt0++;
 84             }
 85             else{
 86                 now=1;
 87                 cnt=cnt0+cnt1;
 88                 while(r!=0 && qcnt1[r]*cnt > qcnt[r]*cnt1 ){
 89                     cnt1+=qcnt1[r];
 90                     cnt+=qcnt[r];
 91                     r--;
 92                 }
 93                 r++;
 94                 qcnt1[r]=cnt1;
 95                 qcnt[r]=cnt;
 96                 cnt0=0;
 97                 cnt1=1;
 98             }
 99         }
100     }
101     if(now==0){
102         cnt=cnt0+cnt1;
103         while(r!=0 && qcnt1[r]*cnt > qcnt[r]*cnt1 ){
104             cnt1+=qcnt1[r];
105             cnt+=qcnt[r];
106             r--;
107         }
108         r++;
109         qcnt1[r]=cnt1;
110         qcnt[r]=cnt;
111     }
112     double te;
113     //printf("  r=%d
",r);
114     while(r!=0){
115         te=1.0*qcnt1[r]/qcnt[r];
116         ans+=(1-te)*(1-te)*qcnt1[r]+te*te*(qcnt[r]-qcnt1[r]);
117         r--;
118     }
119 }
120 
121 void out()
122 {
123     printf("%.6f
",ans);
124 }
125 
126 int main()
127 {
128     //freopen("data.in","r",stdin);
129     scanf("%d",&T);
130    // for(cnt=1;cnt<=T;cnt++)
131     while(T--)
132     //while(scanf("%d",&n)!=EOF)
133     {
134         ini();
135         solve();
136         out();
137     }
138 }