首页 > 代码库 > hdu4923 Room and Moor

hdu4923 Room and Moor

2024-07-16 08:34:15   223人阅读

4923 Room and Moor

Room and Moor

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


Problem Description
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:

 

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

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

Sample Input
491 1 1 1 1 0 0 1 191 1 0 0 1 1 1 1 140 0 1 140 1 1 1
 

Sample Output
1.4285711.0000000.0000000.000000
 

Source
2014 Multi-University Training Contest 6
 

Recommend
hujie

 

题意：输入由1和0组成的A序列，求一个长度与A序列相同的、在实数[0,1]之间的不下降序列B，使得sum of (Ai-Bi)^2最小，输出这个最小的sum。

题解：

先观察一下，发现最左边的0和最右边的1可以忽视，因为我们可以把B左边这段当做0，B右边那段当1。解下来看剩下的。

假如有一段是1111.....00000，由x个1和y个0组成，则这一段最优的B是x/(x+y)，也就是平均值，这可以通过样例看出。

而如果有两段这样的段，111...000 111....000，我们计算两段分别的平均值，若左段小于等于右段，则左段用左段的平均值，右段用右段的平均值是最优的；若左段大于右段，则不能各用各的平均值了，我们把这两段合作一段，用一起的平均值。

根据这个思想，我们把下降的段都合并了，得到平均值上升的若干段，各用各的平均值，哇，最优解！

合并时，从头到尾，相邻的组平均值比较。有可能会出现合并完这两个，新组平均值比再前一个组的平均值还小的情况，所以我们每次合并，都要和之前的比较一发，保证队列不下降。

代码：

  1 //#pragma comment(linker, "/STACK:102400000,102400000")  2 #include<cstdio>  3 #include<cmath>  4 #include<iostream>  5 #include<cstring>  6 #include<algorithm>  7 #include<cmath>  8 #include<map>  9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll __int64 14 #define usint unsigned int 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(int i=0;i<(n);i++) 18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) printf("%d\n",x); 23 #define RE  freopen("D.in","r",stdin) 24 #define WE  freopen("1.out","w",stdout) 25  26 const int maxn=100011; 27  28 struct pig {///分组，每个pig记录一组的和与长度 29     int sum,len; 30     pig(int s,int l) { 31         sum=s; 32         len=l; 33     } 34     pig() {} 35     long double ave() {///还能算平均值，怕不怕 36         return sum*1.0/len; 37     } 38 }; 39  40 pig v[maxn]; 41 int vl,vr; 42 int n; 43 bool a[maxn]; 44  45 int main() { 46     int i,T,j; 47     int l,r; 48     int sum,len; 49     long double ans; 50     int flag; 51     scanf("%d",&T); 52     while(T--) { 53         scanf("%d",&n); 54         for(i=0; i<n; i++) 55             scanf("%d",&a[i]); 56         l=0; 57         r=n; 58         while(a[l]==0&&l<n)l++;///去除左边的0 59         while(a[r-1]==1&&r>=0)r--;///去除右边的1 60         sum=0.0; 61         flag=0; 62         len=0; 63         vl=0; 64         vr=0; 65         for(i=l; i<r; i++) {///将剩下的分成若干组不上升序列，记录各组的和与长度 66             //cout<<i<<‘.‘<<sum<<‘/‘<<len<<endl; 67             if(a[i]==1) { 68                 if(flag==0) 69                     sum++,len++; 70                 else if(flag==1) { 71                     v[vr++]=(pig(sum,len)); 72                     sum=a[i]; 73                     len=1; 74                     flag=0; 75                 } 76             } else if(a[i]==0) { 77                 len++; 78                 if(flag==0) 79                     flag=1; 80             } 81         } 82         if(len>0) v[vr++]=pig(sum,len);///把最后剩下的一组也加入 83         for(i=vl+1; i<vr; i++) { 84             if(v[i-1].ave()>v[i].ave()) {///若相邻两组平均值呈下降，则合并为一组 85                 v[i].sum+=v[i-1].sum; 86                 v[i].len+=v[i-1].len; 87                 v[i-1].sum=0; 88                 v[i-1].len=0; 89                 for(j=i-1; j>=0; j--) 90                     if(v[j].len>0) { 91                         if(v[j].ave()>v[i].ave()) {///有可能合并完后小于更之前的平均值，若发生这种事，则把之前的也合并进来 92                             v[i].sum+=v[j].sum; 93                             v[i].len+=v[j].len; 94                             v[j].sum=0; 95                             v[j].len=0; 96                         } 97                         else break; 98                     } 99             }100         }101         while(v[vl].len==0 && vl<vr) vl++;///去除开头的空组102 //        printf("vl=%d,vr=%d:",vl,vr);103 //        for(i=vl;i<vr;i++)104 //            printf("%.6f,%d ",v[i].sum,v[i].len);105 //        puts("");106         ans=0.0;107         for(i=vl; i<vr; i++) {108             if(v[i].len!=0) {///若为非空组，则统计len*(1-ave)^2+(len-sum)*ave^2109                 //cout<<v[i].sum<<‘,‘<<v[i].len<<‘,‘<<(double)v[i].ave()<<endl;110                 //cout<<(long double)ave<<‘,‘<<(long double)ave2<<‘,‘<<(long double)(len-v[i].sum)<<endl;111                 if(v[i].len>0) ans+=( v[i].ave() * v[i].ave() ) * (v[i].len-v[i].sum) + (1.0-v[i].ave())*(1.0-v[i].ave()) * v[i].sum;112                 //cout<<ans<<endl;113             }114         }115         printf("%.6f\n",(double)ans);116     }117     return 0;118 }
View Code

 


联系
我们