hdu 6070

发表于 | 分类于

分数规划、线段树


题意

给定长度为n的序列，在所有连续子序列中，求（不同数的个数/子序列的长度）的最小值.

  • n<=60000

题解

  • 二分答案mid，检验是否存在一个区间满足 size(l,r)/(r-l+1) ≤ mid，也就是 size(l,r) + mid × l ≤ mid × (r + 1)。
  • 从左往右枚举每个位置作为 r，当 r 变化为 r + 1 时，对 size 的影响是一段区间加 1，线段树维护区间最小值即可。
  • 时间复杂度 O(nlognlogw)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
#define maxn 60010
int dcmp(double x) {
    if(abs(x)<1e-6) return 0;
    return x<0?-1:1;
}
struct SegTree {
    int addv[maxn*4];
    double minv[maxn*4];
    void build(int o,int L,int R,double mid) {
        if(L==R) {
            minv[o]=mid*L;
            addv[o]=0;
        } else {
            int M=(L+R)/2;
            build(o*2,L,M,mid);
            build(o*2+1,M+1,R,mid);
            minv[o]=min(minv[o*2],minv[o*2+1]);
            addv[o]=0;
        }
    }
    void pushdown(int o) {
        addv[o*2]+=addv[o];
        addv[o*2+1]+=addv[o];
        addv[o]=0;
    }
    void maintain(int o,int L,int R) {
        if(L<R) minv[o]=min(minv[o*2],minv[o*2+1]);
        minv[o]+=addv[o];
        if(L==R) addv[o]=0;
    }
    void update(int o,int L,int R,int qL,int qR) {
        if(qL<=L&&R<=qR) {
            addv[o]+=1;
        } else {
            int M=(L+R)/2;
            pushdown(o);
            if(qL<=M) update(o*2,L,M,qL,qR);
            else maintain(o*2,L,M);
            if(qR>M) update(o*2+1,M+1,R,qL,qR);
            else maintain(o*2+1,M+1,R);
        }
        maintain(o,L,R);
    }
    double query(int o,int L,int R,int qL,int qR){
        if(qL<=L&&R<=qR) return minv[o];
        int M=(L+R)/2;
        pushdown(o);
        maintain(o*2,L,M);maintain(o*2+1,M+1,R);
        double ans=1e15;
        if(qL<=M) ans=min(ans,query(o*2,L,M,qL,qR));
        if(qR>M) ans=min(ans,query(o*2+1,M+1,R,qL,qR));
        return ans;
    }
} T;
int pre[maxn],v[maxn];
int main() {
    int ca;
    scanf("%d",&ca);
    while(ca--) {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++) scanf("%d",&v[i]);
        double le=1.0/n,ri=1.0;
        while(ri-le>1e-6) {
            double mid=(le+ri)/2.0;
            bool flag=false;
            memset(pre,0,sizeof(pre));
            T.build(1,1,n,mid);
            for(int i=1; i<=n; i++) {
                T.update(1,1,n,pre[v[i]]+1,i);
                double ans=T.query(1,1,n,1,i);
                if(ans<=mid*(i+1)){
                    flag=true;break;
                }
                pre[v[i]]=i;
            }
            if(flag) ri=mid;
            else le=mid;
        }
        printf("%f\n",le);
    }
    return 0;
}
/*
sz/(R-L+1)<mid
sz+L*mid<(R+1)*mid
*/
/*
2
5
1 2 1 2 3
*/