Dirt Ratio
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 335 Accepted Submission(s): 105
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.
For every problem, you can assume its final submission is accepted.
题意：给你一个长度为n的区间 X=区间不同数的个数 Y=区间长度 求子区间X/Y的最小值
题解：二分答案mid check X/Y<=mid
X/Y=X/(r-L+1)<=mid
=> X+L*mid<=(r+1)*mid
建树初始每个点的maxn为L*mid
从左向右遍历右边界 遍历到r 更新(last[r]+1,r) 值增加1 last[r]表示a[r]相同值的上一个位置
r之前的每个结点L存的是L到r不同数的个数X+L*mid (这些便是不等式的左边）取最小值 与 (r+1)*mid 比较
#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
#define LL long long
#define mod 1000000007
using namespace std;
int t;
int n;
int a[];
int last[];
map<int,int> mp;
struct node
{
int l,r;
double maxn;
int add;
} tree[];
void buildtree(int root ,int left,int right,double zz)
{
tree[root].l=left;
tree[root].r=right;
tree[root].add=;
if(left==right)
{
tree[root].maxn=left*zz;
return ;
}
int mid=(left+right)>>;
buildtree(root<<,left,mid,zz);
buildtree(root<<|,mid+,right,zz);
tree[root].maxn=min(tree[root<<].maxn,tree[root<<|].maxn);
}
void pushdown(int root)
{
if(tree[root].add==) return ;
tree[root<<].add+=tree[root].add;
tree[root<<|].add+=tree[root].add;
tree[root<<].maxn+=tree[root].add;
tree[root<<|].maxn+=tree[root].add;
tree[root].add=;
}
void update(int root,int left,int right,int c)
{
if(tree[root].l==left&&tree[root].r==right)
{
tree[root].add+=c;
tree[root].maxn+=c;
return ;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
{
update(root<<,left,right,c);
}
else
{
if(left>mid)
update(root<<|,left,right,c);
else
{
update(root<<,left,mid,c);
update(root<<|,mid+,right,c); }
}
tree[root].maxn=min(tree[root<<].maxn,tree[root<<|].maxn);
}
double query(int root,int left,int right)
{
if(left>right)
return ;
if(tree[root].l==left&&tree[root].r==right)
{
return tree[root].maxn;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
return query(root<<,left,right);
else
{
if(left>mid)
return query(root<<|,left,right);
else
return min(query(root<<,left,mid),query(root<<|,mid+,right));
}
}
bool check (double x)
{
buildtree(,,n,x);
for(int i=; i<=n; i++)
{
update(,last[i]+,i,);
double zha=(double)query(,,i);
if(zha<=(i+)*x)
return true;
}
return false;
}
int main()
{
scanf("%d",&t);
for(int kk=;kk<=t;kk++){
scanf("%d",&n);
mp.clear();
for(int i=; i<=n; i++){
scanf("%d",&a[i]);
last[i]=mp[a[i]];
mp[a[i]]=i;
}
double l=,r=1.0,mid,ans;
while(abs(l-r)>=0.00001)
{
mid=(l+r)/;
if(check(mid)){
ans=mid;
r=mid;
}
else
l=mid;
}
printf("%f\n",ans);
}
return ;
}