记录第一个五星题

[JSOI2010]缓存交换

https://ac.nowcoder.com/acm/problem/20185

题目

题目描述：

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

解析

解题关键在于当Cache容量已经满的时候优先拿出下一个相同数出现最晚的那个数。倒着遍历一遍存下每一个数上一次出现时的下标（即下一个相同数的坐标），当这个数是最后一次出现时给一个超数据范围的大值即可；因为每次移除的是下一次相同数出现最晚的那个数，可以考虑用优先队列来存数据，然后用一个数组book[i]记录数字i是否在优先队列中，由于主存块编号很大（<=1e9），用map<int,int>映射成小值。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int book[N],Next[N];
map<int,int> M;
struct node{
    int id,nit;
    friend bool operator<(node a,node b){
        return a.nit < b.nit;
    }
}a[N];

priority_queue<node> q;
int main(){
    int n,m,cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].id);
        if(M[a[i].id] == 0)
            M[a[i].id] = ++cnt;
    }
    for(int i=n;i>=1;i--){
        if(Next[M[a[i].id]] == 0)
            a[i].nit=100010;        //a[i].id是最后一个，没有下一个
        else
            a[i].nit=Next[M[a[i].id]];
        Next[M[a[i].id]] = i;
    }
    int sum=0;
    cnt=0;
    for(int i=1;i<=n;i++){
        if(book[M[a[i].id]] == 1){
            q.push(a[i]);          //当a[i].id在队列中时，不会造成内存缺失，这里之所以不把前一个
        }                        //a[i].id从队列中移除是因为它没有当队首的机会
        else{
            ++cnt;
            if(cnt > m){
                --cnt;
                book[M[q.top().id]] = 0;
                q.pop();
            }
            q.push(a[i]);
            book[M[a[i].id]] = 1;
            sum++;
            /*++cnt;
            if(cnt > m){
                --cnt;
                book[M[q.top().id]] = 0;
                q.pop();
            }*/
        }
    }
    cout<<sum<<endl;
}