题目链接

Jessica’s Reading Problem POJ - 3320

思路

$$ 尺取法入门题 $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e6 + 10;
int a[MAXN], b[MAXN], id[MAXN];
int cnt[MAXN];

bool cmp(int x, int y) {
    return a[x] < a[y];
}

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);// don't forget &
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    int cur = id[1];
    b[cur] = 1;
    int tot = 0;
    for (int i = 2; i <= n; i++) {
        cur = id[i];
        int lst = id[i - 1];
        if (a[cur] == a[lst]) {
            b[cur] = b[lst];
        } else {
            b[cur] = b[lst] + 1;
        }
        tot = b[cur];
    }

    int s = 1, t = 1, sum = 0;
    int res = n;
    while (true) {
        while (t <= n && sum < tot) {
            if (cnt[b[t]] == 0) {
                sum++;
            }
            cnt[b[t]]++;
            t++;
        }
        if (sum < tot) {
            break;
        }
        res = min(res, t - s);
        if (cnt[b[s]] == 1) {
            sum--;
        }
        cnt[b[s]]--;
        s++;
    }
    printf("%d", res);
    return 0;
}