Room and Moor

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 539 Accepted Submission(s): 147

Problem Description 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:

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 A _i.
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

Author BUPT

官方题解：

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        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
       
        >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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：杭电 2546 饭卡（01背包）	下一篇：HDU3074_Multiply game(线段树/单..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: