Dirt Ratio 线段树+二分 T13 D43
[传送门]( Problem - 6070 (hdu.edu.cn) )
思路
答案处于 0 - 1 之间
\(cnt(r-l)\)表示l,r区间内不同数得个数
二分答案得到: \(\frac{cnt(r-l)}{r-l+1} \leq mid\)
化简得 $ cnt(r-l) + mid *l \leq mid(r+1)$
枚举 r
则线段树的节点维护的是这个节点到r节点 \(cnt(r-l) + mid *l\) 最小值。
当r=r+1时 ,pre 为r节点数上一次出现的坐标
区间(pre+1,r) 全部加1,表示不同数的个数+1;
参考代码
#include<bits/stdc++.h>
#define db double
#define pb push_back
#define ll long long
#define fi first
#define se second
#define ull unsigned long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (t[p].l+t[p].r)/2
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const int qs=2e5+17;
const int inf = 0x3f3f3f3f;
const db esp = 1e-6;
struct Tree{
int l,r;
db add,val,Min;
#define l(x) t[x].l
#define r(x) t[x].r
#define add(x) t[x].add
#define val(x) t[x].val
}t[qs<<2];
int a[qs],pre[qs],n,T;
void build(int p,int l,int r,db md){
l(p)=l,r(p)=r;
add(p)=0;
val(p)=md*l;
if(l==r) return;
build(ls,l,mid,md);
build(rs,mid+1,r,md);
}
void down(int p){
if(add(p)==0) return;
val(ls)+=add(p);
val(rs)+=add(p);
add(ls)+=add(p);
add(rs)+=add(p);
add(p)=0;
}
void update(int p,int l,int r,db k){
if(l<=l(p)&&r>=r(p)){
val(p)+=k;
add(p)+=k;
return;
}
down(p);
if(l<=mid) update(ls,l,r,k);
if(r>mid) update(rs,l,r,k);
val(p)=min(val(ls),val(rs));
}
db ask(int p,int l,int r){
if(l<=l(p)&&r>=r(p)) return val(p);
down(p);
db val=1e12;
if(l<=mid) val=min(val,ask(ls,l,r));
if(r>mid) val=min(val,ask(rs,l,r));
return val;
}
int ck(db md){
build(1,1,n,md);
for(int i=1;i<=n;++i){
update(1,pre[a[i]]+1,i,1.0);
db fp=ask(1,1,i);
db sum=fp-md*(i+1);
if(sum<esp) return 1;
pre[a[i]]=i;
}
return 0;
}
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i) a[i]=read(),pre[i]=0;
db l=0,r=1,MID,ans=1;
while(r-l>esp){
for(int i=1;i<=n;++i) pre[i]=0;
MID=(r+l)/2;
if(ck(MID)) ans=MID,r=MID;
else l=MID;
}
printf("%.10f\n",ans);
}
return 0;
}
/*
*/
/*
#########
############
#############
## ###########
### ###### #####
### ####### ####
### ########## ####
#### ########### ####
##### ########### #####
###### ### ######## #####
##### ### ######## ######
###### ### ########### ######
###### #### ############## ######
####### ##################### #######
####### ##############################
####### ###### ################# #######
####### ###### ###### ######### ######
####### ## ###### ###### ######
####### ###### ##### #####
###### ##### ##### ####
##### #### ##### ###
##### ;### ### #
## #### ####
*/