HDU 4398 Template Library Management (最优页面调度算法)

中等偏易题。操作系统理论中的最优页面调度算法，贪心。当需要淘汰某个模版时，淘汰掉当前手中在最远的将来才会被用到（或者以后永远不再用到）的那个。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <functional>

 #include <time.h>

 using namespace std;

 typedef pair<int, int> PII;

 const int INF = <<;

 const int MAXN = (int) 1e5+;

 priority_queue<PII> q;

 int Ti[MAXN], next[MAXN];

 int Find[MAXN], len; //离散化用

 int vis[MAXN]; //计算下一次出现用

 bool inq[MAXN]; //判断是否拥有

 int N, M;

 void input() {

     for (int i = ; i < N; i++)

         scanf("%d", &Ti[i]);

 }

 void solve() {

     //离散化

     for (int i = ; i < N; i++)

         Find[i] = Ti[i];

     sort(Find, Find+N);

     len = unique(Find, Find+N) - Find;

     for (int i = ; i < N; i++)

         Ti[i] = lower_bound(Find, Find+len, Ti[i]) - Find;

     //计算next[]

     for (int i = ; i <= len; i++) vis[i] = N+; //初始化vis[]

     for (int i = N-; i >= ; i--) {

         next[i] = vis[Ti[i]];

         vis[Ti[i]] = i;

     }

     int ans = , have = ;

     while (!q.empty()) q.pop(); //初始化队列

     memset(inq, false, sizeof(inq));

     for (int i = , j = ; i < M; i++) { //一开始就有的模板

         int t = Find[j]==(i+) ? j++ : len;

         q.push(make_pair(vis[t], t));

         inq[t] = true;

         have++;

     }

     for (int i = ; i < N; i++) {

         if (!inq[Ti[i]]) { //如果现在没有有这个模板，那么就要去借

             have++;

             ans++;

         }

         //把那个模板拿过来

         inq[Ti[i]] = true;

         q.push(make_pair(next[i], Ti[i]));

         if (have>M) { //需要丢弃模板

             PII x = q.top(); q.pop();

             inq[x.second] = false;

             have--;

         }

     }

     printf("%d\n", ans);

 }

 int main() {

     #ifdef Phantom01

         freopen("I.txt", "r", stdin);

     #endif //Phantom01

     while (scanf("%d%d", &N, &M)!=EOF) {

         input();

         solve();

     }

     return ;

 }