4923Room and Moor
Room and MoorTime Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) 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: 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 Source
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，我们计算两段分别的平均值，若左段小于等于右段，则左段用左段的平均值，右段用右段的平均值是最优的；若左段大于右段，则不能各用各的平均值了，我们把这两段合作一段，用一起的平均值。
根据这个思想，我们把下降的段都合并了，得到平均值上升的若干段，各用各的平均值，哇，最优解！
合并时，从头到尾，相邻的组平均值比较。有可能会出现合并完这两个，新组平均值比再前一个组的平均值还小的情况，所以我们每次合并，都要和之前的比较一发，保证队列不下降。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll __int64
#define usint unsigned int
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,x,n) for(int i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1.out","w",stdout) const int maxn=; struct pig {///分组，每个pig记录一组的和与长度
int sum,len;
pig(int s,int l) {
sum=s;
len=l;
}
pig() {}
long double ave() {///还能算平均值，怕不怕
return sum*1.0/len;
}
}; pig v[maxn];
int vl,vr;
int n;
bool a[maxn]; int main() {
int i,T,j;
int l,r;
int sum,len;
long double ans;
int flag;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(i=; i<n; i++)
scanf("%d",&a[i]);
l=;
r=n;
while(a[l]==&&l<n)l++;///去除左边的0
while(a[r-]==&&r>=)r--;///去除右边的1
sum=0.0;
flag=;
len=;
vl=;
vr=;
for(i=l; i<r; i++) {///将剩下的分成若干组不上升序列，记录各组的和与长度
//cout<<i<<'.'<<sum<<'/'<<len<<endl;
if(a[i]==) {
if(flag==)
sum++,len++;
else if(flag==) {
v[vr++]=(pig(sum,len));
sum=a[i];
len=;
flag=;
}
} else if(a[i]==) {
len++;
if(flag==)
flag=;
}
}
if(len>) v[vr++]=pig(sum,len);///把最后剩下的一组也加入
for(i=vl+; i<vr; i++) {
if(v[i-].ave()>v[i].ave()) {///若相邻两组平均值呈下降，则合并为一组
v[i].sum+=v[i-].sum;
v[i].len+=v[i-].len;
v[i-].sum=;
v[i-].len=;
for(j=i-; j>=; j--)
if(v[j].len>) {
if(v[j].ave()>v[i].ave()) {///有可能合并完后小于更之前的平均值，若发生这种事，则把之前的也合并进来
v[i].sum+=v[j].sum;
v[i].len+=v[j].len;
v[j].sum=;
v[j].len=;
}
else break;
}
}
}
while(v[vl].len== && vl<vr) vl++;///去除开头的空组
// printf("vl=%d,vr=%d:",vl,vr);
// for(i=vl;i<vr;i++)
// printf("%.6f,%d ",v[i].sum,v[i].len);
// puts("");
ans=0.0;
for(i=vl; i<vr; i++) {
if(v[i].len!=) {///若为非空组，则统计len*(1-ave)^2+(len-sum)*ave^2
//cout<<v[i].sum<<','<<v[i].len<<','<<(double)v[i].ave()<<endl;
//cout<<(long double)ave<<','<<(long double)ave2<<','<<(long double)(len-v[i].sum)<<endl;
if(v[i].len>) 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;
//cout<<ans<<endl;
}
}
printf("%.6f\n",(double)ans);
}
return ;
}