题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6070

题意：给个数列，问取一个子序列，子序列里面如果出现相同的数，计数器cnt +1，最后求所有的子序列中cnt/序列长度的最小值。

解法：SB题，我真的SBBBBBBBBBBBBBBBBBBB。。。被虐记。。。


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint()
    {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
const double eps = 1e-6;
const int maxn = 60010;
int n, last[maxn],a[maxn];
struct node{
    int l,r;
    double val,add;
}tree[maxn<<2];
void pushup(int rt){
    tree[rt].val=min(tree[rt*2].val,tree[rt*2+1].val);
}
void pushdown(int rt){
    if(tree[rt].add){
        tree[rt<<1].val=tree[rt<<1].val+tree[rt].add;
        tree[rt<<1|1].val=tree[rt<<1|1].val+tree[rt].add;
        tree[rt<<1].add+=tree[rt].add;
        tree[rt<<1|1].add+=tree[rt].add;
        tree[rt].add=0;
    }
}
void build(int l,int r,int rt, double x){
    tree[rt].l=l,tree[rt].r=r,tree[rt].add=0;
    if(l==r){
        tree[rt].val=1.0*x*l;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,rt*2,x);
    build(mid+1,r,rt*2+1,x);
    pushup(rt);
}
void update(int L,int R,double val, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        tree[rt].val+=val;
        tree[rt].add+=val;
        return;
    }
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(R<=mid) update(L,R,val,rt*2);
    else if(L>mid) update(L,R,val,rt*2+1);
    else{
        update(L,mid,val,rt*2);
        update(mid+1,R,val,rt*2+1);
    }
    pushup(rt);
}
double query(int L, int R, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        return tree[rt].val;
    }
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(R<=mid) return query(L,R,rt*2);
    else if(L>mid) return query(L,R,rt*2+1);
    else{
        return min(query(L,mid,rt*2), query(mid+1,R,rt*2+1));
    }
}
bool check(double mid)
{
    for(int i=1; i<=n; i++) last[i]=0;
    build(1,n,1,mid);
    for(int i=1; i<=n; i++){
        update(last[a[i]]+1,i,1.0,1);
        double mi = query(1,i,1);
        if((mi-mid*(i+1))<=0) return true;
        last[a[i]]=i;
    }
    return false;
}
int main()
{
    int T;
    T = io.xint();
    while(T--){
        n = io.xint();
        for(int i=1; i<=n; i++){
            a[i] = io.xint();
        }
        double l = 0, r = 1.0;
        for(int i=0; i<20; i++){
            double mid = (l+r)/2.0;
            if(check(mid)) r=mid;
            else l=mid;
        }
        printf("%.10f\n", (l+r)/2.0);
    }
    return 0;
}