题意是说给出一组数，在这一组数中找一个区间，使这个区间内AC题数/提交数的值最小。（假设每个区间内最后一次提交都是AC的）
因为保证每个区间都是有题AC的，所以这里可以直接简化为区间内题目种数/区间长度，但在如何更快的处理题目种数的时候一直没能找到合适的处理办法，看了好多博客才能明白这个整体的思路= =（感觉让我自己想怎么都想不出要二分答案....）
首先假设答案为k，区间的题目种数为size,这样就可以得到一个式子size/(r-l+1)=k，但是要直接处理左边的值没有什么好的办法，所以将式子转化一下，可以变成size=(r-l+1)*k，化简成这样还不够，因为这样还是必须要枚举每个区间，所以再进一步转化，改为size+l*k=(r+1)*k，这样的话在处理的时候可以只枚举r，在查询size的时候存入线段树种来进行更新与查询，因为放入了线段树，所以就可以将l*k看作是一个定值，在初始化的时候将线段树的sum直接初始化为l*k再进行计算就可以不用再管l*k的值了。
在线段树更新的时候，每次读入数据的时候记录下他的位置，然后只需去更新他的上个位置+1到现在的位置权值+1就可以确定这个区间的种数了。
但上面的还只是假设，k的值我们是不知道的，但我们知道答案k的区间一定是在[0,1]中的，所以这里可以采用二分的方法，将初始的式子写成size/(r-l+1)<=k，题目中说误差为10^-4，所以只要跑一个循环控制一下精度，然后对于k的值进行二分处理，不断缩小范围，直到条件成立就可以得出结果了。
（PS：这个题好像用的是分数规划的思想，但从来没见过，貌似知道这个思想的都很快想到二分来做了= =改天再去看一下这个东西）
（再PS：代码用的是mid写的k....结合上面的看可能有点乱，见谅见谅= =）
下面AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<climits> using namespace std; const double acc=0.00001; int a[100005]; int pre[100005]; double mid; int n; struct node { int l; int r; double sum; double mark; }s[300005]; void pushup(int k) { s[k].sum=min(s[k<<1].sum,s[(k<<1)+1].sum); } void pushdown(int k) { if(s[k].mark) { s[k<<1].mark+=s[k].mark; s[(k<<1)+1].mark+=s[k].mark; s[k<<1].sum+=s[k].mark; s[(k<<1)+1].sum+=s[k].mark; s[k].mark=0; } } void build(int l,int r,int k) { s[k].l=l; s[k].r=r; s[k].mark=0; if(l==r) { s[k].mark=0; s[k].sum=mid*l; return ; } int mid1=(l+r)/2; build(l,mid1,k<<1); build(mid1+1,r,(k<<1)+1); pushup(k); } double query(int l,int r,int k) { if(l<=s[k].l&&r>=s[k].r) { return s[k].sum; } pushdown(k); int mid3=(s[k].l+s[k].r)/2; double res=INT_MAX; if(l<=mid3) res=min(res,query(l,r,(k<<1))); if(r>mid3) res=min(res,query(l,r,(k<<1)+1)); pushup(k); return res; } void update(int l,int r,int c,int k) { if(l<=s[k].l&&r>=s[k].r) { s[k].mark+=c; s[k].sum+=c; return ; } pushdown(k); int mid2=(s[k].l+s[k].r)/2; if(l<=mid2) update(l,r,c,k<<1); if(r>mid2) update(l,r,c,(k<<1)+1); pushup(k); } int check() { int i; double k; memset(pre,0,sizeof(pre)); build(1,n,1); for(i=1;i<=n;i++) { k=mid*(i+1.0); update(pre[a[i]]+1,i,1,1); if(query(1,i,1)<=k) return 1; pre[a[i]]=i; } return 0; } int main() { int T; int i,j; double ans; double l,r; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } l=0; r=1; ans=1; while(r-l>=acc) { mid=(l+r)/2.0; if(check()) { ans=mid; r=mid-acc; } else l=mid+acc; } printf("%.10f\n",ans); } return 0; }