Room and Moor

PM Room defines a sequence A = {A₁, A₂,..., A_N}, each of which is either 0 or 1. In order to beat him, programmer Moor has to construct another sequence B = {B₁, B₂,... , B_N} of the same length, which satisfies that:

4
9
1 1 1 1 1 0 0 1 1
9
1 1 0 0 1 1 1 1 1
4
0 0 1 1
4
0 1 1 1

1.428571
1.000000
0.000000
0.000000

官方题解：

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef __int64 ll;
struct node
{
    double l,r;
    double p;
} b[50010];

int main()
{
    int T;
    cin>>T;
    int n;
    int s[100100];
    while(T--)
    {
        cin>>n;
        double ans=0;
        bool flag=true;
        for(int i=0; i<n; i++)
        {
            cin>>s[i];
            if(s[i]==0&&flag) i--,n--;
            else flag=false;
        }
        int l=0,r=n-1;
        for(; r>=0; r--)
        if(s[r]!=1)
        {
            break;
        }
        int k=1;
        b[0].p=0;
        b[1].l=0,b[1].r=0;
        for(int i=l; i<=r; i++)
        {
            if(s[i]==1) b[k].l++;
            else b[k].r++;

            b[k].p=b[k].l/(b[k].l+b[k].r);
            while(b[k].p<b[k-1].p)
            {
                b[k-1].l+=b[k].l;
                b[k-1].r+=b[k].r;
                b[k-1].p=b[k-1].l/(b[k-1].l+b[k-1].r);
                b[k].l=0,b[k].r=0;
                k--;
            }
            k++;
            b[k].l=0,b[k].r=0;
        }
        for(int i=1; i<k; i++)
        {
            ans+=b[i].r*b[i].p;
        }
        printf("%.6lf\n",ans);
    }
    return 0;
}

hdu 4923 Room and Moor,布布扣,bubuko.com

hdu 4923 Room and Moor

原文：http://blog.csdn.net/knight_kaka/article/details/38434165