一开始是有不少 simple 的想法的...
比如剩余使用次数越多越优或者越少越劣这样
随便找找反例发现这显然是不行的
比如一个点之前用的很少但在最后用的很多，
如果我还一直保留他那中间过程中的可用位置就变少了
可能会导致很多出现次数较少但比较集中的物品被反复拿多次
针对这种情况，有一个贪心策略就是下次出现的越早的物品留着越优
貌似也没什么反例（我也不会证明
这样就每个需求记录一下下一次出现的位置
用堆维护，在堆满时将最劣的物品弹掉
这时我非常激动地无脑码就 GG 成 10 pts 了
在仔细考虑会不会出锅后，会发现如果在需要一个物品而它又恰好在堆中时，
什么操作也不用做，但在这之后这个物品就永远地留在了堆里，
而且他永远不会成为堆顶（k = 1 不影响）
所以应该每次发现当前需求物品在堆中后 ++k
代码：
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 100005, MAXP = 500005;
struct ITEM{
int nxt, id;
ITEM(int NXT = 0, int ID = 0) {nxt = NXT; id = ID;}
bool operator < (const ITEM& b) const {
return nxt < b.nxt;
}
};
int n, k, p, ans;
int req[MAXP], pos[MAXN], nxt[MAXP];
bool inq[MAXN];
priority_queue<ITEM> q;
inline int rd() {
register int x = 0;
register char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) {
x = x * 10 + (c ^ 48);
c = getchar();
}
return x;
}
int main() {
n = rd(); k = rd(); p = rd();
for (int i = 1; i <= p; ++i)
req[i] = rd();
for (int i = p; i; --i) {
nxt[i] = ((pos[req[i]]) ? pos[req[i]] : (p + 1));
pos[req[i]] = i;
}
for (int i = 1; i <= p; ++i) {
if (!inq[req[i]]) {
if (q.size() == k) {
inq[q.top().id] = false;
q.pop();
}
q.push(ITEM(nxt[i], req[i]));
inq[req[i]] = true;
++ans;
} else {
++k;
q.push(ITEM(nxt[i], req[i]));
}
}
printf("%d\n", ans);
return 0;
}
BZOJ1528: [POI2005]sam-Toy Cars
原文：https://www.cnblogs.com/xcysblog/p/9813453.html