poj3320: 爬行法, 卡 IO

poj3320.md

Poj 3320

題目

分析

爬行法。

這題有卡 IO，需使用 scanf/printf。 先用 set 取得總數量，再用爬行法。

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int data[1000000];

int main() {
    //ios::sync_with_stdio(false);

    int P;
    scanf("%d", &P);

    vector<int> data(P);
    for (int i = 0; i < P; i++)
        scanf("%d", &data[i]);

    set<int> all;
    for (int i = 0; i < P; i++)
        all.insert(data[i]);
    const int N = all.size();

    // 爬行法
    // [s, t)
    int s = 0;
    int t = 0;
    int num = 0;
    map<int, int> cnt;
    int ans = P;

    for (;;) {
        while (t < P && num < N) {
            if (cnt[data[t]] == 0)
                num++;
            cnt[data[t++]]++;
        }

        if (num < N)
            break;

        if (t - s < ans)
            ans = t - s;

        if (cnt[data[s]] == 1)
            num--;
        cnt[data[s++]]--;
    }

    printf("%d\n", ans);

    return 0;
}