题意：
给你一个A数列，让你求一个单调递增的B数列(0<=bi<=1)，使得sum{(ai-bi)^2}最小。
思路：
很明显，如果A = 0...01...1，那么bi=ai即可。
可以证明，如果 A = 1...10...0，那么所有bi达到同一个值的时候取得最优值。 假设 ai = 1, aj = 0， 那么 i<j ，所以bi<=bj。 若bi != bj，那么增大bi的值，或者减小bj的值都可以得到更优的结果。 所以，bi=bj。
所以，如果A数列里面出现了形如 "1...10...0"的部分，我们都可以把它当做同一段处理。因为他们对应的bi值一定相同。
这样，我们可以得到一个中间序列，x1, ..., x1, x2, ..., x2, ..., xm, ...xm. 我们可以把它简化为，x1, ..., xm。其中 xi对应着每一段的最优值。
我们可以发现，这里的xi不一定单调递增。 然后我们仿照上面的证明，知道当有相邻两段的xi递减时，会在他们所有的bi相等时取得最优值。因此，我们可以把这两段合并，求出一个满足单调性的值。
所以，最后的B序列一定是这样：y1, ..., y1, ..., ym, ..., ym。所以我们可以用一个单调栈来维护所有的bi值。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <time.h> using namespace std; typedef pair<double, int> PDI; const int INF = <<;
const int MAXN = (int) 1e5+; int n;
int a[MAXN];
double b[MAXN]; PDI sk[MAXN]; //栈
int tail; //栈顶指针 void solve() {
tail = ; //栈初始化 for (int i = ; i < n; i++) {
sk[tail++] = make_pair(1.0*a[i], ); //当前点入栈
while (tail> && sk[tail-].first<=sk[tail-].first) { //如果栈不满足单调性，合并最上面两个节点
int cnt = sk[tail-].second+sk[tail-].second;
double tmp = (sk[tail-].first*sk[tail-].second+sk[tail-].first*sk[tail-].second)/cnt;
sk[tail-] = make_pair(tmp, cnt);
tail--;
}
}
//求出bi
for (int i = , j = ; i < tail; i++)
for (int k = ; k < sk[i].second; k++)
b[j++] = sk[i].first;
//求出结果
double ans = ;
for (int i = ; i < n; i++)
ans += (a[i]-b[i])*(a[i]-b[i]);
printf("%f\n", ans);
} int main() {
#ifdef Phantom01
freopen("HDU4923.txt", "r", stdin);
#endif //Phantom01 int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
solve();
} return ;
}
HDU 4923