首页 > 代码库 > hdu4923 Room and Moor
hdu4923 Room and Moor
4923 Room and Moor
Room and MoorTime 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。