HDU-6070-二分+线段树Dirt Ratio

360 阅读 0 评论 238 点赞

我是靠谱客的博主欣慰便当，这篇文章主要介绍HDU-6070-二分+线段树Dirt Ratio，现在分享给大家，希望可以做个参考。

Dirt Ratio

Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2522 Accepted Submission(s): 1138
Special Judge

Problem Description

In ACM/ICPC contest, the ''Dirt Ratio'' of a team is calculated in the following way. First let's ignore all the problems the team didn't pass, assume the team passed

X problems during the contest, and submitted Y times for these problems, then the ''Dirt Ratio'' is measured as X Y . If the ''Dirt Ratio'' of a team is too low, the team tends to cause more penalty, which is not a good performance.

Picture from MyICPC

Little Q is a coach, he is now staring at the submission list of a team. You can assume all the problems occurred in the list was solved by the team during the contest. Little Q calculated the team's low ''Dirt Ratio'', felt very angry. He wants to have a talk with them. To make the problem more serious, he wants to choose a continuous subsequence of the list, and then calculate the ''Dirt Ratio'' just based on that subsequence. Please write a program to find such subsequence having the lowest ''Dirt Ratio''.

Input

The first line of the input contains an integer

T (1 \leq T \leq 15), denoting the number of test cases. In each test case, there is an integer n (1 \leq n \leq 60000) in the first line, denoting the length of the submission list. In the next line, there are n positive integers a 1, a 2, . . ., a n (1 \leq a i \leq n), denoting the problem ID of each submission.

Output

For each test case, print a single line containing a floating number, denoting the lowest ''Dirt Ratio''. The answer must be printed with an absolute error not greater than

10 - 4 .

Sample Input

1 5 1 2 1 2 3

Sample Output

0.5000000000

Hint

For every problem, you can assume its final submission is accepted.

Source

2017 Multi-University Training Contest - Team 4

求一个序列中的连续子序列S，使得（S中不同元素的个数）/（S的长度）最小化。挺不错的一道题，很考验思维。对于这种最小化的题目很容易往二分上面想，得到 a/b<=k ,我们只要不断二分k，找到下界即可，问题是对于k如何判定是否可行，枚举所有区间显然不靠谱，考虑这个式子 diff(l,r)/(r-l+1)<=k -> diff(l,r)+k*l<=k*(r+1), 我们可以枚举一下右端点，然后找到一个最优的左端点判断能否使得这个不等式成立即可，可以用线段树区间修改来维护这个值，结点 u(L,R),保存的就是[L,R]中最小的 diff(l,r)+k*l ,显然l€[L,R]。初始化根节点为k*L,然后遍历右端点的时候更新对应的区间，也就是会对那些区间的diff造成变化。


1 #include<iostream>

2 #include<cstring>

3 #include<queue>

4 #include<cstdio>

5 #include<stack>

6 #include<set>

7 #include<map>

8 #include<cmath>

9 #include<ctime>
 10 #include<time.h>
 11 #include<algorithm>
 12 #include<bits/stdc++.h>
 13 using namespace std;
 14 #define mp make_pair
 15 #define pb push_back
 16 #define debug puts("debug")
 17 #define LL long long
 18 #define pii pair<int,int>
 19 #define inf 0x3f3f3f3f
 20
 21 #define mid ((L+R)>>1)
 22 #define lc (id<<1)
 23 #define rc (id<<1|1)
 24 #define eps 1e-5
 25 const int _M=60006;
 26 double sum[_M<<2];
 27 int laz[_M<<2];
 28 int a[_M],x[_M],pre[_M];
 29 void pushdown(int id){
 30
if(laz[id]){
 31
laz[lc]+=laz[id];
 32
laz[rc]+=laz[id];
 33
sum[lc]+=laz[id];
 34
sum[rc]+=laz[id];
 35
laz[id]=0;
 36 
}
 37 }
 38 void pushup(int id){
 39
sum[id]=min(sum[lc],sum[rc]);
 40 }
 41 void build(int id,int L,int R,double k){
 42
if(L==R){
 43
sum[id]=k*L;
 44
return;
 45 
}
 46 
build(lc,L,mid,k);
 47
build(rc,mid+1,R,k);
 48 
pushup(id);
 49 }
 50 void update(int id,int L,int R,int l,int r){
 51
if(L>=l&&R<=r){
 52
sum[id]++;
 53
laz[id]++;
 54
return ;
 55 
}
 56 
pushdown(id);
 57
if(l<=mid) update(lc,L,mid,l,r);
 58
if(r>mid) update(rc,mid+1,R,l,r);
 59 
pushup(id);
 60 }
 61 double query(int id,int L,int R,int l,int r){
 62
if(L>=l&&R<=r){
 63
return sum[id];
 64 
}
 65 
pushdown(id);
 66
if(r<=mid) return query(lc,L,mid,l,r);
 67
else if(l>mid) return query(rc,mid+1,R,l,r);
 68
else return min(query(lc,L,mid,l,r),query(rc,mid+1,R,l,r));
 69 
pushup(id);
 70 }
 71 bool ok(double k,int n){
 72
memset(sum,0,sizeof(sum));
 73
memset(laz,0,sizeof(laz));
 74
build(1,1,n,k);
 75
for(int i=1;i<=n;++i){
 76
update(1,1,n,pre[i]+1,i);
 77
if(query(1,1,n,1,i)<=k*(i+1)) return 1;
 78 
}
 79
return 0;
 80 }
 81 int main(){
 82
int t,n,m,i,j;
 83
scanf("%d",&t);
 84
while(t--){
 85
scanf("%d",&n);
 86
memset(x,0,sizeof(x));
 87
for(i=1;i<=n;++i) {
 88
scanf("%d",a+i);
 89
pre[i]=x[a[i]];
 90
x[a[i]]=i;
 91 
}
 92
 93
double l=0,r=1.0;
 94
while(abs(l-r)>eps){
 95
double k=(l+r)/2;
 96
if(ok(k,n)) r=k;
 97
else l=k+eps;
 98 
}
 99
printf("%.10fn",l);
100 
}
101
return 0;
102 }