现在的位置: 首页 > 综合 > 正文

hdu 4923 Room and Moor 贪心+YY

2019年09月04日 ⁄ 综合 ⁄ 共 1833字 ⁄ 字号 评论关闭

Room and Moor

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 350    Accepted Submission(s): 103



Problem Description
PM Room defines a sequence A = {A1, A2,..., AN}, each of which is either 0 or 1. In order to beat him, programmer Moor has to construct another sequence B = {B1, B2,... , BN} of the same length,
which satisfies that:

 


Input
The input consists of multiple test cases. The number of test cases T(T<=100) occurs in the first line of input.

For each test case:
The first line contains a single integer N (1<=N<=100000), which denotes the length of A and B.
The second line consists of N integers, where the ith denotes Ai.

 


Output
Output the minimal f (A, B) when B is optimal and round it to 6 decimals.
 


Sample Input
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
 


Sample Output
1.428571 1.000000 0.000000 0.000000
 


Source

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000+100;
int n,flag,num,now; // now为[1111...000]这种形式区间的个数,num记录1的个数,flag是当前为0的标志
int a[MAXN],cnt[MAXN][2],sum[MAXN][2];
void init()
{
    num=now=0; flag=1;
    memset(cnt,0,sizeof(cnt));
}
int main()
{
    //freopen("text.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i] == 0){
               cnt[now][0]++;
               if(!flag)
                    flag=1;
            }
            else {
                num++;
                if(flag){
                    ++now; flag=0;
                    cnt[now][1]++;
                }
                else
                    cnt[now][1]++;
            }
        }
        if(cnt[now][0] == 0){  // 剔除尾端全是1的情况
            num-=cnt[now][1]; --now;
        }
        if(now == 0){
            printf("%.6f\n",0.0);
            continue;
        }
        sum[0][0]=sum[0][1]=0;
        for(int i=1;i<=now;i++){
            sum[i][0]=sum[i-1][0]+cnt[i][0];
            sum[i][1]=sum[i-1][1]+cnt[i][1];
        }
        int x=1;
        double ans=0.0;
        while(x<=now){
             double p=0;
             int i=x,pos=x;
             while(i<=now){
                double q=(sum[i][0]-sum[x-1][0])*1.0/(sum[i][0]-sum[x-1][0]+sum[i][1]-sum[x-1][1]);
                if(q>p){
                    p=q; pos=i;
                }
                i++;
             }
             int cnt1=sum[pos][0]-sum[x-1][0]; //记录区间0的个数
             int cnt2=sum[pos][1]-sum[x-1][1]; // 记录区间1的个数
             ans+=(1-p)*(1-p)*cnt1+p*p*cnt2;
             x=pos+1;
        }
        printf("%.6f\n",ans);
    }
    return 0;
}

抱歉!评论已关闭.