题意：
给定一个长度为n的，由0和1组成的序列ai，求一个序列bi，使得∑(bi-ai)^2最小。其中0<=bi<=1,bi<=b(i+1)，bi为浮点型。输出最小的∑(bi-ai)^2的值。
思路：显然开头为0的的部分和结尾为1的部分不用考虑
然后把其他序列划分成多个11111000形式的区域（这步也需要YY），每个区域分别求出bi（因地制宜的YY2333），求bi是二次函数的对称轴，如果bi不满足递增要求，比如bi-1>bi，所以如果不改变bi-1，bi至少要增大至bi-1才损失最小，一旦增大到bi-1又可以用二次函数模型，可以得到合并bi-1和bi的总区间再求bx会损失更小，万一合并后的bx也不满足递增关系那就继续合并综合判断还是比原来的损失小.
当然也有可能改变bi-1通过bi-1和bi-2合并的方式，这样YY下去最后会得到bi-2，bi-1，bi三个区间合并了，没必要损失bi-2，，不可取这种方式来改变化bi-1
正确性已准确证明
//2024 KB1310 msC++1370 B#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int inf= 0x3f3f3f3f;const int N =1e5+100;int a[N],num[N],len[N];int main(){int T;scanf("%d",&T);while(T–){int n,i;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&a[i]);int st=1 , ed=n ;while(a[st]==0) st++;while(a[ed]==1) ed–;int l=0;double ans=0;while(st<=ed){int cnt=0;for(i=st;i<=ed;i++){if(i!=st&&a[i]>a[i-1]){num[++l]=cnt;len[l]=i-st;st=i;break;}if(a[i]==1) cnt++;if(i==ed){num[++l]=cnt;len[l]=i-st+1;st=i+1;break;}}while(l!=1&&(double)num[l]/len[l]<(double)num[l-1]/len[l-1]){num[l-1]+=num[l];len[l-1]+=len[l];l–;}}for(i=1;i<=l;i++){double val=(double)num[i]/len[i];ans+=val*val*(len[i]-num[i])+(1-val)*(1-val)*num[i];}printf("%.6f\n",ans);}return 0;}
飞机一阵抖动，我终于说出了最后一句再见。
