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:
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; }