codeforces 802B Heidi and Library (medium)

题目链接：http://codeforces.com/contest/802/problem/B

题意：一个书店的n天借阅记录，然后给你图书馆藏书容量k，如果你要看一本书，发现书店没有，就需要丢弃其中的一本书，然后购买需要的书。。。。。问你最少需要购买多少本书（刚开始书店没有书）

分析：这种题一看就是需要贪心。对于每次需要丢弃的书的决策，我们需要尽量保证丢弃的书在最近不会被用到，如果你今天丢了，明天就需要用，那你就需要再买回来。因此我们在每次丢弃书时，选取以后最晚借阅的书进行丢弃。

AC代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int a[400005];
  4 int b[400005];
  5 bool d[400005];
  6 map<int, int>mp;
  7 queue<int>q[400005];
  8 struct st {
  9     int num;
 10     int ed;
 11     st(int _num, int _ed) {
 12         num = _num;
 13         ed = _ed;
 14     }
 15 };
 16 bool operator < (st a, st b) {
 17     return a.ed < b.ed;
 18 }
 19 priority_queue<st>pq;
 20 int main() {
 21     ios_base::sync_with_stdio(0);
 22     //freopen("out1.txt","w",stdout);
 23     int n, k;
 24     memset(b, 0, sizeof(b));
 25     memset(d, 0, sizeof(d));
 26     cin >> n >> k;
 27 
 28     for(int i = 1; i <= n; i++) {
 29         cin >> a[i];
 30     }
 31 
 32     int ans = 0;
 33     int num = 0;
 34     int i;
 35 
 36     for(i = 1; i <= n; i++) {
 37         if(num < k) {
 38             if(d[a[i]] == 0) {
 39                 num++;
 40                 d[a[i]] = 1;
 41                 b[num] = a[i];
 42             }
 43         }
 44         else break;
 45     }
 46 
 47     if(num < k) {
 48         cout << num << endl;
 49     }
 50     else {
 51         int result = k;
 52 
 53         for(int j = i; j <= n; j++) {
 54             q[a[j]].push(j);
 55         }
 56 
 57         for(int j = 1; j <= k; j++) {
 58             if(q[b[j]].empty()) {
 59                 pq.push(st(j, 400005));
 60             }
 61             else {
 62                 int dd = q[b[j]].front();
 63                 pq.push(st(j, dd));
 64             }
 65             mp[b[j]] = j;
 66         }
 67 
 68         for(i; i <= n; i++) {
 69             if(d[a[i]] == 0) {
 70                 int id;
 71                 st aa = pq.top();
 72                 id = aa.num;
 73                 d[b[id]] = 0;
 74                 d[a[i]] = 1;
 75                 b[id] = a[i];
 76                 pq.pop();
 77 
 78                 if(!q[a[i]].empty()) {
 79                     q[a[i]].pop();
 80                 }
 81 
 82                 mp[a[i]] = id;
 83 
 84                 if(!q[a[i]].empty()) {
 85                     pq.push(st(id, q[a[i]].front()));
 86                 }
 87                 else {
 88                     pq.push(st(id, 400005));
 89                 }
 90 
 91                 result++;
 92             }
 93             else {
 94                 if(!q[a[i]].empty()) q[a[i]].pop();
 95 
 96                 if(!q[a[i]].empty()) {
 97                     pq.push(st(mp[a[i]], q[a[i]].front()));
 98                 }
 99                 else {
100                     pq.push(st(mp[a[i]], 400005));
101                 }
102             }
103         }
104 
105         cout << result << endl;
106     }
107 
108     return 0;
109 }

View Code