HDU 4923 Room and Moor 贪心+栈

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

题意：，Bi可以是小数。

思路：很机智的想法，对于连续M个1+N个0的一块来说，最优解一定是，Bi=M/（M+N），因为Bi是递增的（可以手推），所以如果出现在后面的一块中的Bi>前面一块的Bi，那么就不可能取到最优解，所以将两块合并一起处理，这样过程中就需要用栈来维护了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#include <set>
#define PI acos(-1.0)
#define maxn 105
#define INF 0x7fffffff
#define eps 1e-8
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int aa[1000005];
struct Line
{int t0,t1;double val;void calc(){val=(double)t1/(double)(t1+t0);}double sum(){return val*val*(double)(t0)+(1-val)*(1-val)*(double)(t1);}
} l[1000005],h;
int main()
{int T;scanf("%d",&T);while(T--){memset(l,0,sizeof(l));memset(aa,0,sizeof(aa));int tot,head=-1,tail=-1;scanf("%d",&tot);for(int i=0; i<tot; i++)scanf("%d",&aa[i]);for(int i=0; i<tot; i++)if(aa[i]==1){head=i;break;}for(int i=tot-1; i>=0; i--)if(aa[i]==0){tail=i;break;}if(tail<=head)printf("0.000000\n");else{int t=head,top=0;while(t<tail){for(int i=t;i<=tail;i++)if(aa[i]==0){l[top].t1=i-t;t=i;break;}for(int i=t;i<=tail;i++){if(i==tail){l[top].t0=i-t+1;t=i;break;}else if(aa[i]==1){l[top].t0=i-t;t=i;break;}}l[top].calc();top++;}stack < Line > st;while(!st.empty())st.pop();for(int i=0;i<top;i++){if(st.empty())st.push(l[i]);else{while(!st.empty()&&st.top().val>l[i].val){h=st.top();st.pop();l[i].t0+=h.t0;l[i].t1+=h.t1;l[i].calc();}st.push(l[i]);}}double ans=0;while(!st.empty()){h=st.top();ans+=h.sum();st.pop();}printf("%.6lf\n",ans);}}return 0;
}