题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4923
解题报告：给出一个长度为n的只包含0和1的序列，是否存在一个序列Bi满足一下条件：
1. 0 <= B[i] <= 1
2. B[i] <= B[i+1]
3. f(A,B) = ∑(i=1-n) (A[i] - B[i])^2
4. f(A,B)最小是多少
前面的0可以直接去掉，后面的1可以直接去掉，然后剩下中间形如1 1 0 0的序列，在这样的区间中前后的B[i]很明显应该是相等才能保证最小的，
我们可以先分别求出每段这样的区间的B[i]，然后维护一个单调队列，当要插入的B[i]大于等于队尾的B[i]，则直接插入，当要插入的小于队尾的B[i],
则将队尾的那个区间跟现在要插入的区间合并然后求出一个新的B[i]代替，得到新的B[i]之后注意又要跟队尾比较。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
#define maxn 100005
struct node
{
int a,b;
double x;
}B[maxn];
int A[maxn];
deque<node> que;
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = ;i <= n;++i)
scanf("%d",&A[i]);
while(n >= && A[n] == ) //把后面的1去掉
n--;
int s = ;
while(s <= n && A[s] == )
s++;
if(s >= n)
{
printf("%.6lf\n",);
continue;
}
A[] = ;
int f = ;
for(int i = s;i <= n;++i)
{
if(A[i] == )
{
if(A[i-] == && A[i] == )
{
f++;
B[f].a = B[f].b = ; //初始化 }
B[f].a++;
}
else B[f].b++; }
for(int i = ;i <= f;++i) //遍历一遍，计算出每节的x应该是多少
B[i].x = (double)B[i].a / (double)(B[i].a + B[i].b); // for(int i = 1;i <= f;++i)
// printf("a = %d b = %d x = %.6lf\n",B[i].a,B[i].b,B[i].x);
que.clear();
node temp;
deque<node>::iterator iter;
for(int i = ;i <= f;++i) //维护一个单调队列
{
if(que.empty() || B[i].x >= que.begin()->x)
que.push_front(B[i]);
else
{
while(!que.empty() && B[i].x < que.begin()->x)
{
B[i].a += que.begin()->a;
B[i].b += que.begin()->b;
B[i].x = (double)B[i].a / (double)(B[i].a + B[i].b);
que.pop_front();
}
i--; //为了在下一次循环中，把这个节点插入到队列中
}
}
double tot = ;
for(iter = que.begin();iter != que.end();++iter)
tot += ((double)iter->a * (1.0 - iter->x) * (1.0 - iter->x) + (double)iter->b * iter->x * iter->x);
printf("%.6lf\n",tot);
}
return ;
}