题目链接：

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

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

AC代码：

1 #include
      
         2 using namespace std;  3 int a[400005];  4 int b[400005];  5 bool d[400005];  6 map
       
        mp;  7 queue
        
         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
         
          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 }