[JSOI2010]缓存交换

题目背景

感谢@ACdreamer 贡献数据

题目描述

在计算机中，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缺失次数。

输入格式

输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。

第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

输出格式

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

样例 #1

样例输入 #1

6 2
1 2 3 1 2 3

样例输出 #1

提示

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

说实话这道题真的迷到我了

首先看一眼数据范围，这不离散化怎么做是不是

所以……

map<int, int> li;
int cnt = 0;
for (int i = 1; i <= n; i++) {
    scanf("
    if (li[a[i]])
        continue;
    li[a[i]] = ++cnt;
}

贪心的思路不用多说，如果当前 cache 满了，就把 cache 中下一次出现最晚的替换掉，需要注意的是，如果当前 cache 中已经有了需要访问的主存块，则需要更新此主存块下一次访问的时间。

我的第一个想法是对于每个主存块建立一个栈，逆序存储出现的次数，依次向后推进，但是对于已经存在的主存块的更新，第一反应是用指针，然而蒟蒻并不会，但是我发现如果不将已存在的主存块更新，而是直接加入一个新的元素并将 cache 上限 $+1$ ，可以获得相同的效果，于是有了 $30$ 分代码 emmmm

所以，用栈是不行滴，只要对每一位求出当前位对应编号下一次出现的时间即可

部分代码如下：

int now[maxn];
memset(now, 0x7f, sizeof(now));
for (int i = n; i >= 1; i--) {
    b[i] = now[li[a[i]]];
    now[li[a[i]]] = i;
}

最后正向推进一遍就可以啦

完整代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>

using namespace std;

#define maxn 100100

struct poi {
    int s /*离散化后序号*/, nex /*下一次出现*/;
    bool operator<(const poi& b) const { return b.nex > nex; }
};
priority_queue<poi> cache /*cache*/;

map<int, int> li; /*离散化*/

int b[maxn]; /*下一次出现*/
int a[maxn];
bool vis[maxn];

int main() {
    int n, m;
    scanf("

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        scanf("
        if (li[a[i]])
            continue;
        li[a[i]] = ++cnt;
    }

    int now[maxn];
    memset(now, 0x7f, sizeof(now));
    for (int i = n; i >= 1; i--) {
        b[i] = now[li[a[i]]];
        now[li[a[i]]] = i;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[li[a[i]]] == 0) {
            ans++;
            if (cache.size() == m) {
                vis[cache.top().s] = 0;
                cache.pop();
            }
            cache.push((poi){li[a[i]], b[i]});
            vis[li[a[i]]] = 1;
        } else {
            m++;
            cache.push((poi){li[a[i]], b[i]});
        }
    }
    printf("
    return 0;
}