题目地址：洛谷：【P4404】[JSOI2010]缓存交换 – 洛谷、BZOJ：Problem 1826. — [JSOI2010]缓存交换

题目描述

在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。
例如，当前Cache容量为3，且已经有编号为10和20的主存单元。 此时，CPU访问编号为10的主存单元，Cache命中。
接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。
接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编号为10的主存单元。
接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避免本次访问的缺失。
在现代计算机中，往往采用LRU(最近最少使用)的算法来进行Cache调度——可是，从上一个例子就能看出，这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少的Cache缺失次数。

题意简述

cache容量有限，当CPU想访问某一cache中不存在的数据时，如果cache已满，需要从中扔掉一块数据再读入，现在希望求出最小的这种cache miss的次数。

输入输出格式

输入格式：
输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。
第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

输出格式：
输出一行，为Cache缺失次数的最小值。

输入输出样例

输入样例#1：

6 2
1 2 3 1 2 3

输出样例#1：

4

说明

在第4次缺失时将3号单元换出Cache。

题解

跟[POI2005]SAM-TOY CARS是一个题。只不过这里值域比较大需要离散化或者像我一样强行map/set用上去。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 500005;

std::set<int> inque;

int n, k, a[MAXN];
std::map<int, int> nxt, head;

struct cmp {
    inline bool operator()(const int &a, const int &b) {
        return nxt[a] < nxt[b];
    }
};

std::priority_queue<int, std::vector<int>, cmp> pq;

int main() {
    n = readint(); k = readint(); 
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        nxt[head[a[i]]] = i; head[a[i]] = i;
    }
    for(std::map<int, int>::iterator it = head.begin(); it != head.end(); it++) {
        nxt[it->second] = 1e9;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!inque.count(a[i])) {
            if(pq.size() == k) {
                inque.erase(a[pq.top()]); pq.pop();
            }
            inque.insert(a[i]); ans++;
        } else {
            k++;
        }
        pq.push(i);
    }
    printf("%d", ans);
    return 0;
}