做题感悟:比赛做这题是只考虑到前面 0 和后面 1 是没有用的其它的方面就没想法了,看了题解才明白……
解体思路:
首先考虑到的应该是前面的 0 和后面的 1 是没有用处的 ,那么剩下的就是前面是 1 ,后面是 0 的若干段 10 串,可以先分别处理每一段。
这里每一段的数列中的值都是一样的且是平均数,解释一下:先解释为什么都是同一个数,假设某10串 有 x 个 1 ,y 个 0 ,那么这个串可以用两个数 bi ,bj 就可以,因为前面都是 1 ,后面都是 0 ,假设 bi < bj 那么,如果 bj ,不变化 bi 增大一点但不超过 bj ,这样得到的结果显然将会变的更小一点,那么,bi == bj 就是最佳状态了,好了,为什么都是一个
B 值解释清楚了,那又为什么取平均数呢?? 假设这串数列都取了 bi 作为 B 数列的值,那么会得到 ( 1 - bi ) ^ 2 + (1 - bi ) ^ 2 + (1 - b i ) ^2……bi ^2 + bi^2 + bi^ 2 ,好了,这样肯定看不出什么东东的,让我们化简一下会得到,( x + y ) * bi ^ 2 - 2 * x * a + x ,然后把 bi 当成未知数,那么很明显这是一个二元一次方程,且开口向上,那么bi 取 ( - b ) / (2 * a) 时取得最小值,代入得
: x / (x + y ) ,这个式子正好求的就是上面那个串的平均值。
其实处理的时候完全可以边输入边处理,只要某段的bi 不大于前一段的 bj ,就将这两段的值合并。
代码(参考了某大牛代码):
#include<iostream> #include<fstream> #include<iomanip> #include<ctime> #include<fstream> #include<sstream> #include<stack> #include<cstring> #include<cmath> #include<map> #include<vector> #include<cstdio> #include<algorithm> #define INT __int64 using namespace std ; const double esp = 0.00000001 ; const int mod = 1e9 + 7 ; const int MY = 1000 + 10 ; const int MX = 100000 + 10 ; double num[MX] ,len[MX] ; int main() { int Tx ,n ; scanf("%d" ,&Tx) ; while(Tx--) { scanf("%d" ,&n) ; int cnt = 0 ; double x ; for(int i = 0 ;i < n ;i++) { scanf("%lf" ,&x) ; num[cnt] = x ; 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 ; for(int i = 0 ;i < cnt ;i++) { double y = num[i]/len[i] ; ans += num[i]*(1.0-y)*(1.0-y) + (len[i]-num[i])*y*y ; } cout<<fixed<<setprecision(6)<<ans<<endl ; } return 0 ; }