本文主要是介绍HDU 4923 Room and Moor，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：比赛做这题是只考虑到前面 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 ;
}
这篇关于HDU 4923 Room and Moor的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
