題意：
? ? ? ?給你序列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\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4923 f(A,B)分段处理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。