NC20185 [JSOI2010]缓存交换

这是一道堆的题，堆的题常与贪心有关，此题也是。
借鉴别人的博客 + 别人的代码给整明白了，于是乎自己写篇博客再理理思路
首先这个题肯定是要在下标上做文章，因为要判断当前数是否在缓存区内，我们可以用一个bool数组，而这个数组肯定存第i个数在不在缓存区内，所以bool[i]的这个i就是指第i个数，不能指i这个数在不在缓存区内，因为最大值1e9，开不了那么大的数组，而找到第i个数下一次出现的数组nexti同样。

思路：
1.大体思路：
我们把前m个数放到缓存区后，再碰到不在缓存区里的数时，我们需要删除一个原来在缓存区的数，然后把这个数加到缓存区内，首先问题在于删除那个数，我首先想到删除后面出现少的那个数，但这不对，反例如下：
1000 3
12 15 16 14 12 15 14 12 15 后面的数全是16
对于这个样例，如果对于14这个数，用上面的思路一定不删16，而实际上删16最划算，因为你不管删12还是15，在后面的几个数中你都要频繁的删数，而删16的话，紧跟着后面的这几个数不需要删除，后面的一坨16也只需要处理一次即可。
正确的贪心是，把缓存区中元素中下一次出现最晚的那个给删除了，所以我们需要一个数组来存第i个数的下一次出现在哪里，要一直找最晚的我们需要一个堆等等
2.需要维护什么？代码具体怎么写？
根据上面的分析我们需要维护这么几个容器：
（1）.bool型数组boo[i]，表示第i个数在不在缓存区内
（2）.int型数组nexti[i] (这个很离谱，我定义为next时牛客编译不过，自己编译器过了，改了个名好了)，存第i个数下一次出现的位置
（3）.堆q
（4）.map<int,int> mp这个一开始妹李姐。
这个map是基于当前位置i，从n到1找ar[i]最后一次出现的位置（注意这个顺序n ~ 1），即基于当前位置向后找第一次出现ar[i]的位置（有点绕，感觉又是把5星难度东西说成了8星）
需要维护的变量：
（1）.num 当前缓存区内元素个数
（2）.ans 答案
代码提纲：
看别人代码后自己整理思路写了个提纲，要不然自己写的时候还有点脑子不够用想看别人的代码
1.维护nexti数组
我们需要知道元素ar[i],即第i个数下一次出现在哪里。我们需要从n到1遍历，原因是那个map。
判断ar[i]这个数是不是最后一次出现，是最后一次出现则，nexti[i]中存一个很大的数
不是则存下一次出现的位置mp[ar[i]] 当时不李姐为什么mp[ar[i]]就是下一次出现的位置)
最后更新mp[ar[i]]的值
2.从1~n开始遍历

判断第i个数在不在缓存区内
    不在（ans++）
        num<k,
        需要做三件事，1.num++。2.第i个数下次出现的位置置为1。3.把下一次出现的位置放到堆里
        否则，
        四件事，1.取堆顶并pop。2.改变boo数组。3.同上面的2。4.同上面的3
    在
        更新boo，更新堆（不需要取出i，因为i永远不可能在堆顶了）。

AC代码：

#include <bits/stdc++.h>

using namespace std;

int n, m;
map<int,int> mp;
bool boo[100050];
int nexti[100050];
int ar[100050];
priority_queue<int> q;
int num, ans;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
    for(int i = n; i > 0; --i)
    {
        if(mp[ar[i]] == 0)  nexti[i] = 100050;
        else    nexti[i] = mp[ar[i]];
        mp[ar[i]] = i;
    }
    for(int i = 1; i <= n; ++i)
    {
        if(boo[i] == 0)
        {
            ans++;
            if(num < m)
            {
                num++;
                boo[nexti[i]] = 1;
                q.push(nexti[i]);
            }
            else
            {
                boo[q.top()] = 0;
                q.pop();
                boo[nexti[i]] = 1;
                q.push(nexti[i]);
            }
        }
        else
        {
            boo[nexti[i]] = 1;
            q.push(nexti[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}