求最小的 区间数的个数/区间大小
二分答案 ，线段树验证（题意感觉很迷）
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #define lson (rt<<1) #define rson (rt<<1|1) #define eps 1e-9 using namespace std; const int MAXN=60000+10; double mi[MAXN*4]; double add[MAXN*4]; int pre[MAXN],mk[MAXN],a[MAXN]; int n;int cnt=0; void build(int l,int r,int rt,double x){ // printf("%d\n",rt); add[rt]=0; if(l==r){ mi[rt]=l*x; return ; } int mid=l+r>>1; build(l,mid,lson,x); build(mid+1,r,rson,x); mi[rt]=min(mi[lson],mi[rson]); } void update(int l,int r,int x,int y,int rt){ // printf("%d\n",cnt++); if(l==x&&r==y){ mi[rt]+=1.0; add[rt]+=1.0; return ; } if(add[rt]!=0.0){ mi[lson]+=add[rt]; mi[rson]+=add[rt]; add[lson]+=add[rt]; add[rson]+=add[rt]; add[rt]=0.0; } int mid=l+r>>1; if(mid>=y)update(l,mid,x,y,lson); else if(x>mid)update(mid+1,r,x,y,rson); else update(l,mid,x,mid,lson),update(mid+1,r,mid+1,y,rson); mi[rt]=min(mi[lson],mi[rson]); } double query(int l,int r,int y,int rt){ if(r==y)return mi[rt]; if(add[rt]!=0.0){ mi[lson]+=add[rt]; mi[rson]+=add[rt]; add[lson]+=add[rt]; add[rson]+=add[rt]; add[rt]=0.0; } int mid=l+r>>1; if(mid>=y)return query(l,mid,y,lson); else return min(mi[lson],query(mid+1,r,y,rson)); mi[rt]=min(mi[lson],mi[rson]); } bool isok(double x){ build(1,n,1,x); for(int i=1;i<=n;i++){ update(1,n,pre[i]+1,i,1); double mi=query(1,n,i,1); if(mi<=(i+1)*x)return 1; } return 0; } int main() { // freopen("1004.in","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++)pre[i]=0,mk[a[i]]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); pre[i]=mk[a[i]]; mk[a[i]]=i; } double l=0.0,r=1.0,ans=1.0; for(int i=1;i<=20;i++){ double mid=(l+r)*0.5; if(isok(mid)){ r=mid-eps; ans=mid; } else { l=mid+eps; } } printf("%.10f\n",ans); } return 0; }