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
1.428571 1.000000 0.000000 0.000000
题意：给了你一个A序列由0，1组成，然后让你找一个等长的B序列使得对应数差的平方和是最小的
思路：最后得到的数列的形如{x1, x1, x2, x2 ..... xn, xn}，且{x1 < x2 < ... < xn}，首先我们可以得到某段区间[xl, xl+1, .. xr]和是
∑(xl, xr) (xi-x)^2, 我们可以知道他是一个形如:ax^2+bx+c 的函数，所以我们可以得到最小值的x是这个区间数的平均值，我们将过程模拟成栈，那么扫描入栈一个我们就判断它求的x与栈顶的值时候满足非递减的关系，不是的话我们合并，处理完后求值就行了
num[i]表示该区间1的个数，len[i]表示该区间的长度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
double num[maxn], len[maxn];
int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
int cnt = 0, a;
for (int i = 0; i < n; i++) {
scanf("%d", &a);
num[cnt] = a;
len[cnt++] = 1;
while (cnt >= 2) {
if (num[cnt-1]/len[cnt-1] > num[cnt-2]/len[cnt-2])
break;
num[cnt-2] += num[cnt-1];
len[cnt-2] += len[cnt-1];
cnt--;
}
}
double ans = 0.0;
for (int i = 0; i < cnt; i++) {
double tmp = num[i]/len[i];
ans += tmp*tmp*(len[i]-num[i]) + (1-tmp)*(1-tmp)*num[i];
}
printf("%.6lf\n", ans);
}
return 0;
}HDU 4923 Room and Moor,布布扣,bubuko.com
原文：http://blog.csdn.net/u011345136/article/details/38424541