题解 P2058 【海港】

2018-08-06 19:31:31


为什么我不用队列都一次过,明明很简单,按题意模拟就行了呀 QAQ~

只要维护一个 std::unordered_map<int, int>,对于每一艘船,判断是否有船只到达时间超过 $24$ 小时,如果有就把当前船上的所有乘客的国籍从 std::unordered_map<int, int> 中删除,然后再统计当前到达的船上乘客的国籍,最后输出 std::unordered_map<int, int> 的大小,就 A 了呀 QWQ~

PS:因为数据太大, $x_{i, j}$ 要动态分配内存。

下面是萌萌哒代码(用了 fread 快读,事实上并不需要):

#include <cstdio>
#include <cctype>
#include <unordered_map>

const int MaxN = 1e5;
const int Limit = 1e5;
const int DaySec = 86400;

char next() {
    static const size_t BufSize = 1 << 17;
    static char *fs, *ft, buf[BufSize];

    if (fs == ft) {
        ft = (fs = buf) + fread(buf, 1, BufSize, stdin);

        if (fs == ft) return EOF;
    }

    return *fs++;
}

int nextInt() {
    int x = 0;
    char c;
    while (!isdigit(c = next()));
    while (isdigit(c)) { x = x * 10 + c - '0'; c = next(); }

    return x;
}

int main() {
    int n;
    n = nextInt();

    static int t[MaxN + 1], k[MaxN + 1];
    static int *x[MaxN + 1];
    for (int i = 1; i <= n; ++i) {
        t[i] = nextInt();
        k[i] = nextInt();
        x[i] = new int[ k[i] ];
        for (int j = 0; j < k[i]; ++j) x[i][j] = nextInt();
    }

    int p = 1;
    std::unordered_map<int, int> cnt;
    for (int i = 1; i <= n; ++i) {
        while (!(t[i] - DaySec < t[p])) {
            for (int j = 0; j < k[p]; ++j) if (--cnt[ x[p][j] ] == 0) cnt.erase(x[p][j]);
            ++p;
        }

        for (int j = 0; j < k[i]; ++j) ++cnt[ x[i][j] ];

        printf("%d\n", cnt.size());
    }
}