首页 > 代码库 > hdu 4923 Room and Moor
hdu 4923 Room and Moor
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 = {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.
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
Author
BUPT
官方题解:
代码:
#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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。