hdu 4923 Room and Moor

http://acm.hdu.edu.cn/showproblem.php?pid=4923

在A序列中，对于非递增{1,1,1.....0,0}这样的序列，最优解是取这一段的平均数。而对于多段这样的区间{1,1,1...0,1,1,1...0,0}，我们需要进行两两合并，合并后最优解是这整个区间的平均数。

因此我们拿一个栈去保存每一段的xi，顺次枚举Ai，首先要判断它是否要与前面的xi合并，若栈顶的xi大于它，那么需要依次与栈内的xi合并直到不满足条件，否则Ai直接入栈。

<pre name="code" class="cpp">#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;
const int maxn = 100010;struct node
{double sum; //这一段的和int len;//这一段的长度node(){}node(double sum1, int len1){sum = sum1;len = len1;}
};stack <struct node> st;int a[maxn];
int main()
{int test;scanf("%d",&test);while(test--){int n;int len;double sum,x;scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&a[i]);while(!st.empty()) st.pop();for(int i = 1; i <= n; i++){if(!st.empty() && st.top().sum/st.top().len >= a[i]) //满足条件，合并{len = 1;sum = a[i];while(!st.empty() && st.top().sum/st.top().len >= sum/len){len += st.top().len;sum += st.top().sum;st.pop();}st.push(node(sum,len));}else st.push(node(a[i],1)); }double ans = 0;while(!st.empty()){x = st.top().sum / st.top().len;ans += (1-x)*(1-x)*st.top().sum + x*x*(st.top().len-st.top().sum);st.pop();}printf("%.6lf\n",ans);}return 0;
}