页面

发表于 更新于 分类于

Problem’s Website

  • 页面

    Solution

  • 这道题听说是算法导论中的原题，是一道贪心题，如果内存已满，那我们就用当前内容替换内存中下一次出现最远的内容，我们可以用一个数组把当前内容下一次出现的位置记录下来，用STL堆来维护内存。

    Code

    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
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #define gc getchar()
    #define pc(x) putchar(x)
    #define re register
    const int Maxn = 200000 + 10;
    inline int sc() {
        int xx = 0, ff = 1; char cch = gc;
        while(!isdigit(cch)) {
            if(cch == '-') ff = -1; cch = gc;
        }
        while(isdigit(cch)) {
            xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
        }
        return xx * ff;
    }
    inline void out(int x) {
        if(x < 0) pc('-'), x = -x;
        if(x >= 10)
            out(x / 10);
        pc(x % 10 + '0');
    }
    int n, k, ans;
    int a[Maxn], lst[Maxn], nxt[Maxn];
    bool pd[Maxn];
    std :: priority_queue <std :: pair <int, int> > q, in;
    int main() {
    //	freopen("page.in", "r", stdin);
    //	freopen("page.out", "w", stdout);
    	n = sc(), k = sc();
    	for(re int i = 1; i <= n; ++i) {
    		a[i] = sc();
    		nxt[lst[a[i]]]=i;
    		lst[a[i]]=i;
    	}
    	for(re int i = 1; i <= Maxn - 10; ++i) {
    		if(lst[i]) nxt[lst[i]] = n + 1;
    	}
    	int cnt = 0;
    	for(re int i = 1; i <= n; ++i) {
    		if(pd[a[i]]) {
    			in.push(std :: make_pair(i, a[i]));
    			q.push(std :: make_pair(nxt[i], a[i]));
    			continue;
    		}
    		if(cnt < k) {
    			pd[a[i]] = 1;
    			q.push(std :: make_pair(nxt[i], a[i]));
    			++ans;
    			++cnt;
    		}
    		else {
    			while(!q.empty() && !in.empty() && q.top() == in.top())
    				q.pop(), in.pop();
    			int top = q.top().second; q.pop();
    //			std :: cerr << top << std :: endl;
    			pd[top] = 0, pd[a[i]] = 1;
    			q.push(std :: make_pair(nxt[i], a[i]));
    			++ans;
    		}
    	}
    	out(ans), pc('\n');
        return 0;
    }
    // Coded by dy.

rp++