描述 Description
Jasio 是一个三岁的小男孩, 他最喜欢玩玩具了, 他有 n 个不同的玩具, 它们都被放在了很高的架子上所以 Jasio 拿不到它们. 为了让他的房间有足够的空间, 在任何时刻地板上都不会有超过 k 个玩具. Jasio 在地板上玩玩具. Jasio’的妈妈则在房间里陪他的儿子. 当 Jasio 想玩地板上的其他玩具时, 他会自己去拿, 如果他想玩的玩具在架子上, 他的妈妈则会帮他去拿, 当她拿玩具的时候, 顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间. 他的妈妈很清楚自己的孩子所以他能够预料到 Jasio 想玩些什么玩具. 所以她想尽量的使自己去架子上拿玩具的次数尽量的少, 应该怎么安排放玩具的顺序呢?
输入格式 InputFormat
第一行三个整数: n, k, p (1 <= k <= n <= 100.000, 1 <= p <= 500.000), 分别表示玩具的总数, 地板上玩具的最多个数以及 Jasio 他想玩玩具的序列的个数, 接下来 p 行每行描述一个玩具编号表示 Jasio 想玩的玩具.
输出格式 OutputFormat
一个数表示 Jasio 的妈妈最少要拿多少次玩具.
样例输入 SampleInput
10 3 20
1
2
3
2
3
4
5
4
3
5
1
5
6
8
10
9
8
9
10
6
样例输出 SampleOutput
11
CodeChef 某次月赛有这题的弱化版 ->[ccAUG14] Cleaning Tables。
对于每次地面上已满的话找到下一次最迟玩的那个玩具放回架子上，预处理出每个玩具下一次使用的时间，用个优先队列（大根堆）维护即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define pa pair<int,int>
const int inf=0x7fffffff/27.11;
const int maxn=100005;
const int maxp=500005;
int i,j,t,n,m,l,r,k,z,y,x;
pa a[maxp],tp;
int last[maxn];
bool used[maxn],inq[maxn];
priority_queue <pa> q;
int p,ans;
int main()
{
scanf("%d%d%d",&n,&k,&p);
for (i=1;i<=p;i++) scanf("%d",&a[i].second);
for (i=p;i>0;i--) a[i].first=(last[a[i].second]!=0)?last[a[i].second]:inf,last[a[i].second]=i;
ans=m=0;
for (i=1;i<=p;i++)
{
if (!used[a[i].second])
{
ans++;
used[a[i].second]=true;
if (m<k)
{
m++;
}
else
{
while (!used[q.top().second]) q.pop();
tp=q.top();q.pop();
used[tp.second]=false;
}
}
q.push(a[i]);
}
printf("%d\n",ans);
return 0;
}