来自大佬的讲解：http://blog.csdn.net/jerans/article/details/76651326
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=6070
题意：
定义一个区间的值为（不同数的个数/区间长度），求所有区间内的最小值
有一种01分数规划的思想，二分结果值now，这样只要存在一个区间使得这个值<=now,即可
也就是 dif/(r-l+1)<=now , 这样要使dif/(r-l+1)部分尽量的小，并不好确定，转换一下
dif<=(r-l+1)*now 依旧不好确定，因为这样还是除了枚举所有的l，r，并没有什么好思路，枚举转移也不好做，如果能分开l和r，按一定顺序枚举l或r，是不是就有一些可以重复利用的东西
dif+l*now<=(r+1)*now
这样O(n)枚举每一个r，并且要快速的确定dif+l*now的最小值，l*now是个固定值，dif的求法可以用线段树实现，这样也能快速的求这两者加和的最小
线段树里保存的是每个点到当前枚举的r之间的dif值，记录每一个数和他相同的且在他之前的最后一次出现的下标pre，每次通过线段树更新pre【a【r】】和r之间(左开右闭)加一，这样就能保证每个相同的数在同一个区间内对dif的贡献只有一次。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 60010;
const double eps = 1e-7;
double mid;
int pre[maxn], a[maxn], n;
struct SegTree
{int l, r;double val, lazy;
}seg[maxn<<2];
void pushup(int rt)
{seg[rt].val = min(seg[rt<<1].val, seg[rt<<1|1].val);return ;
}
void pushdown(int rt)
{if(seg[rt].lazy){seg[rt<<1].lazy += seg[rt].lazy;seg[rt<<1|1].lazy += seg[rt].lazy;seg[rt<<1].val += seg[rt].lazy;seg[rt<<1|1].val += seg[rt].lazy;seg[rt].lazy = 0;}return ;
}
void build(int rt, int l, int r)
{if(l == r){seg[rt].lazy = 0;seg[rt].val = mid * l;return ;}seg[rt].lazy = 0;int m = (l + r) >> 1;build(rt<<1, l, m);build(rt<<1|1, m+1, r);pushup(rt);return ;
}
void update(int l, int r, int left, int right, int rt)
{if(l <= left && r >= right){seg[rt].val++;seg[rt].lazy++;return ;}pushdown(rt);int m = (left + right) >> 1;if(m >= l)update(l, r, left, m, rt<<1);if(m < r)update(l, r, m+1, right, rt<<1|1);pushup(rt);return ;
}
double query(int l, int r, int left, int right, int rt)
{if(l <= left && r >= right)return seg[rt].val;pushdown(rt);int m = (left + right) >> 1;double res = 1e18;if(m >= l)res = min(res, query(l, r, left, m, rt<<1));if(m < r)res = min(res, query(l, r, m+1, right, rt<<1|1));pushup(rt);return res;
}
bool check()
{memset(pre, 0, sizeof(pre));build(1, 1, n);for(int i = 1; i <= n; i++){double tmp = mid * (i+1.0);update(pre[a[i]]+1, i, 1, n, 1);if(query(1, i, 1, n, 1) <= tmp)return true;pre[a[i]] = i;}return false;
}
int main()
{int t;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);double ans = 1, left = 0, right = 1.0;while(right - left >= eps){mid = (left + right) * 0.5;if(check()){ans = mid;right = mid - eps;}elseleft = mid + eps;}printf("%.10f\n", ans);}return 0;
}