中等偏易题。操作系统理论中的最优页面调度算法，贪心。当需要淘汰某个模版时，淘汰掉当前手中在最远的将来才会被用到（或者以后永远不再用到）的那个。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <time.h> 15 16 using namespace std; 17 18 typedef pair<int, int> PII; 19 20 const int INF = 1<<30; 21 const int MAXN = (int) 1e5+11; 22 23 priority_queue<PII> q; 24 int Ti[MAXN], next[MAXN]; 25 int Find[MAXN], len; //离散化用 26 int vis[MAXN]; //计算下一次出现用 27 bool inq[MAXN]; //判断是否拥有 28 int N, M; 29 30 void input() { 31 for (int i = 0; i < N; i++) 32 scanf("%d", &Ti[i]); 33 } 34 35 void solve() { 36 //离散化 37 for (int i = 0; i < N; i++) 38 Find[i] = Ti[i]; 39 sort(Find, Find+N); 40 len = unique(Find, Find+N) - Find; 41 for (int i = 0; i < N; i++) 42 Ti[i] = lower_bound(Find, Find+len, Ti[i]) - Find; 43 44 //计算next[] 45 for (int i = 0; i <= len; i++) vis[i] = N+1; //初始化vis[] 46 for (int i = N-1; i >= 0; i--) { 47 next[i] = vis[Ti[i]]; 48 vis[Ti[i]] = i; 49 } 50 51 int ans = 0, have = 0; 52 while (!q.empty()) q.pop(); //初始化队列 53 memset(inq, false, sizeof(inq)); 54 for (int i = 0, j = 0; i < M; i++) { //一开始就有的模板 55 int t = Find[j]==(i+1) ? j++ : len; 56 q.push(make_pair(vis[t], t)); 57 inq[t] = true; 58 have++; 59 } 60 61 for (int i = 0; i < N; i++) { 62 if (!inq[Ti[i]]) { //如果现在没有有这个模板，那么就要去借 63 have++; 64 ans++; 65 } 66 //把那个模板拿过来 67 inq[Ti[i]] = true; 68 q.push(make_pair(next[i], Ti[i])); 69 70 if (have>M) { //需要丢弃模板 71 PII x = q.top(); q.pop(); 72 inq[x.second] = false; 73 have--; 74 } 75 } 76 77 printf("%d ", ans); 78 } 79 80 int main() { 81 #ifdef Phantom01 82 freopen("I.txt", "r", stdin); 83 #endif //Phantom01 84 85 while (scanf("%d%d", &N, &M)!=EOF) { 86 input(); 87 solve(); 88 } 89 90 return 0; 91 }