给你序列A，让你构造序列B然后求出最小的f(A <B),其中A 是0，或者1组成的，而B是[0,1]的实数，f(A,B) = 求和(i从1到n) （Ai - Bi）^ 2.
思路：
首先有一点很明确，那就是我们可以消除面连续的0，和后面连续的1，一开始我的想法是直接求中间部分的平均数， 然后就前面的连续0不用管，后面的连续1不用管，然后中间的部分就是平均数，结果妥妥的WA了，其实正解是分段处理，分成这样的 111000,10
，1110,1111100000...就是断成一些连续1加连续0组成的小段，然后对于当前的这一段的最优就是当前这段的平均数，但是有一点要注意，题目要求的是非递减顺序，那么如果当前的这一段的平均数比前面的那一段的小，我们就得把一段和上一段合并，合并之后如果还比上上一段小，那么在合并（这个地方可以用一个栈，比较方便写），最后在根据剩下的段数来计算答案，既保证了最小，有保证了上升。
#include<stdio.h> #include<string.h> #include<stack> using namespace std; typedef struct { double s0 ,s1; }NODE; int num[110000]; NODE node[110000]; int main () { int n ,t ,i ,s11 ,mk; scanf("%d" ,&t); while(t--) { scanf("%d" ,&n); for(s11 = 0 ,i = 1 ;i <= n ;i ++) { scanf("%d" ,&num[i]); if(num[i]) s11 ++; } for(mk = n + 1 ,i = 1 ;i <= n ;i ++) if(num[i]) {mk = i;break;} if(s11 == n || mk == n + 1) { puts("0.000000"); continue; } int tt = 0; double s1 = 0 ,s0 = 0; num[n+1] = 1; for(i = mk ;i <= n ;i ++) { if(num[i]) s1 ++; else s0 ++; if(!num[i] && num[i+1]) { node[++tt].s1 = s1; node[tt].s0 = s0; s1 = s0 = 0; } } stack<NODE>st; NODE xin ,tou; for(i = 1 ;i <= tt ;i ++) { if(st.empty()) { st.push(node[i]); continue; } xin = node[i]; tou = st.top(); double tp = tou.s1 / (tou.s1 + tou.s0); double xp = xin.s1 / (xin.s1 + xin.s0); if(xp < tp) { while(1) { tou = st.top(); st.pop(); xin.s1 += tou.s1; xin.s0 += tou.s0; if(st.empty()) { st.push(xin); break; } tou = st.top(); tp = tou.s1 / (tou.s1 + tou.s0); xp = xin.s1 / (xin.s1 + xin.s0); if(xp >= tp) { st.push(xin); break; } } } else st.push(node[i]); } double ans = 0; while(!st.empty()) { NODE tou = st.top(); st.pop(); double tp = tou.s1 / (tou.s1 + tou.s0); ans += (1 - tp) * (1 - tp) * tou.s1 + tp * tp * tou.s0; } printf("%.6lf " ,ans); } return 0; }