[HDU6070] Dirt Ratio

Problem Link

Description

    给出一个长度为 n 的序列，寻找一个区间，X表示这个区间不同元素的个数， Y 表示区间的长度，求y=XY的最小值。

Solution

    暴力是 O(n2) 的，枚举左端点和右端点即可。对于求分数最值的问题，我们很容易想到二分答案（因为之前写过好多道这样的题目）。但最重要的不是想到二分，而是如何 check ，在这之前我们要先学会移项，假设当前要 check 的答案是 mid ，我们要使 mid 能成为答案，只要使 XY≤mid ，即 size[L,R]R−L+1≤mid ，移项可得 size[L,R]+L∗mid≤(R+1)∗mid 。接下来说说怎么 check ，我们知道不可能同时枚举 L 和R的，只能枚举一维，另一维要么 O(1) ，要么 O(logn) ， O(1) 感觉不可能，不如想想 O(logn) 的。 我们枚举 R 的话，只要能求出的值最小的L即可，那就可以用线段树维护了，每次 R 向右枚举时对一段区间 1，然后每次query出最小值，再跟 (R+1)∗mid 比较即可。

Code

#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #define M 60005 #define P 10000 using namespace std; template <class T> inline void Rd(T &res){ char c;res=0;int k=1; while(c=getchar(),c<48&&c!='-'); if(c=='-'){k=-1;c='0';} do{ res=(res<<3)+(res<<1)+(c^48); }while(c=getchar(),c>=48); res*=k; } template <class T> inline void Pt(T res){ if(res<0){ putchar('-'); res=-res; } if(res>=10)Pt(res/10); putchar(res%10+48); } struct node{ int L,R,mi,add; }tree[M<<2]; int T; int n; int A[M]; void up(int p){ tree[p].mi=min(tree[p<<1].mi,tree[p<<1|1].mi); } void down(int p){ if(!tree[p].add)return; tree[p<<1].add+=tree[p].add; tree[p<<1].mi+=tree[p].add; tree[p<<1|1].add+=tree[p].add; tree[p<<1|1].mi+=tree[p].add; tree[p].add=0; } void build(int L,int R,int p,int lim){ tree[p].L=L;tree[p].R=R;tree[p].add=0; if(L==R){ tree[p].mi=L*lim; return; } int mid=(L+R)>>1; build(L,mid,p<<1,lim); build(mid+1,R,p<<1|1,lim); up(p); } void update(int L,int R,int p){ if(tree[p].L==L&&tree[p].R==R){ tree[p].add+=P; tree[p].mi+=P; return; } down(p); int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid)update(L,R,p<<1); else if(L>mid)update(L,R,p<<1|1); else{ update(L,mid,p<<1);update(mid+1,R,p<<1|1); } up(p); } int query(int L,int R,int p){ if(tree[p].L==L&&tree[p].R==R)return tree[p].mi; down(p); int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid)return query(L,R,p<<1); if(L>mid)return query(L,R,p<<1|1); return min(query(L,mid,p<<1),query(mid+1,R,p<<1|1)); } int pos[M]; bool check(int lim){ memset(pos,0,sizeof(pos)); build(1,n,1,lim); for(int i=1;i<=n;i++){ update(pos[A[i]]+1,i,1); pos[A[i]]=i; int res=query(1,i,1); if(res<=(i+1)*lim)return true; } return false; } int main(){ Rd(T); while(T--){ Rd(n); for(int i=1;i<=n;i++)Rd(A[i]); int L=0,R=P,res=0; while(L<=R){ int mid=(L+R)>>1; if(check(mid)){ res=mid; R=mid-1; }else L=mid+1; } printf("%.4lf",1.0*res/P); putchar('\n'); } return 0; }

    个人感觉二分是蛮好想到的，但是这个 check 的方式有点新颖，枚举 R <script type="math/tex" id="MathJax-Element-26">R</script>，再用线段树维护最小值， 这就是算法+数据结构的厉害之处。