地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=6070
题面:
Dirt Ratio
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1599 Accepted Submission(s): 740
Special Judge
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''.
In each test case, there is an integer n(1≤n≤60000) in the first line, denoting the length of the submission list.
In the next line, there are n positive integers a1,a2,...,an(1≤ai≤n), denoting the problem ID of each submission.
5
1 2 1 2 3
For every problem, you can assume its final submission is accepted.
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=6e4+;
const int mod=1e9+; int n,a[K],pre[K],b[K];
double v[*K],lz[*K];
void push_down(int o)
{
v[o<<]+=lz[o],v[o<<|]+=lz[o];
lz[o<<]+=lz[o],lz[o<<|]+=lz[o];
lz[o]=;
}
double update(int o,int l,int r,int pos,double x)
{
if(l==r) return v[o]=x;
int mid=l+r>>;
push_down(o);
if(pos<=mid) update(o<<,l,mid,pos,x);
else update(o<<|,mid+,r,pos,x);
v[o]=min(v[o<<],v[o<<|]);
}
double update2(int o,int l,int r,int nl,int nr,double x)
{
if(l==nl && r==nr) return v[o]+=x,lz[o]+=x;
int mid=l+r>>;
push_down(o);
if(nr<=mid) update2(o<<,l,mid,nl,nr,x);
else if(nl>mid) update2(o<<|,mid+,r,nl,nr,x);
else update2(o<<,l,mid,nl,mid,x),update2(o<<|,mid+,r,mid+,nr,x);
v[o]=min(v[o<<],v[o<<|]);
}
bool check(double mid)
{
for(int i=,mx=n*;i<=mx;i++) v[i]=1e9,lz[i]=;
for(int i=;i<=n;i++)
{
update(,,n,i,i*mid);
update2(,,n,pre[i]+,i,1.0);
if(v[]<(i+)*mid+eps) return ;
}
return ;
}
int main(void)
{
int t;cin>>t;
while(t--)
{
scanf("%d",&n);
memset(b,,sizeof b);
for(int i=;i<=n;i++) scanf("%d",a+i),pre[i]=b[a[i]],b[a[i]]=i;
double l=,r=;
for(int i=;i<=;i++)
{
double mid=(l+r)/2.0;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.6f\n",l);
}
return ;
}