sam-Toy Cars

sam-Toy Cars( 贪心\(\star\star?\))

• 时限：\(1s\) 内存：\(256M\)

Descrption

• \(Jasio\) 是一个三岁的小男孩，他最喜欢玩玩具了，他有 \(n\) 个不同的玩具，它们都被放在了很高的架子上，所以\(Jasio\) 拿不到它们。为了让他的房间有足够的空间，在任何时刻地板上都不会有超过 \(k\) 个玩具（\(Jasio\) 在地板上玩玩具）。
• \(Jasio\) 的妈妈则在房间里陪他的儿子。当 \(Jasio\) 想玩地板上的其他玩具时，他会自己去拿。如果他想玩的玩具在架子上，他的妈妈则会帮他去拿。当她拿玩具的时候，顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间。他的妈妈很清楚自己的孩子，所以他能够预料到 \(Jasio\) 想玩些什么玩具。所以她想尽量的使自己去架子上拿玩具的次数尽量的少，应该怎么安排放玩具的顺序呢？

Input

• 第一行三个整数：\(n, k, p (1 <= k <= n <= 10^5, 1 <= p <= 5\times 10^5)\)，分别表示玩具的总数、地板上玩具的最多个数以及 \(Jasio\) 他想玩玩具的序列的个数。
• 接下来 \(p\) 行每行描述一个玩具编号，表示 \(Jasio\) 想玩的玩具。

Output

• 一个数表示 \(Jasio\) 的妈妈最少要拿多少次玩具。

Sample Input

3 2 7
1
2
3
1
3
1
2

Sample Output

4

Hint

• \(30\%\) 的数据满足 \(1<=n<=500,1<=k<=200,1<=p<=2000\)
• \(50\%\) 的数据满足 \(1<=n<=5000,1<=k<=2000,1<=p<=40000\)
• \(100\%\) 的数据满足 \(1 <= k <= n <= 100,000, 1 <= p <= 500,000\)
• 来源：\(luoguSP688\)

分析

• 最近做的贪心也比较多了，此题的贪心也不难想，显然地上没有就拿一个，如果地上空间还够直接拿就行，如果地上的玩具已经有 \(k\) 个了就需要把地上的一个玩具放到架子上去，麻烦的就是究竟这 \(k\) 件玩具应该放哪一件？
• 究竟选择哪件放到架子取决于，当前物品下次使用时间，如果下次使用的时间最晚，显然就应该先把他放上去，所以我们需要维护每个时刻当前物品下次使用的时刻，我们以用类似邻接表的方式，倒序对这 \(m\) 次的玩具使用情况进行维护，\(nxt[i]\) 表示第 \(i\) 次玩的玩具 \(a[i]\) 下一次玩的时间。
• 实现步骤：
  1. 倒序预处理出 \(nxt[i]\)。
  2. \(1\sim m\) 遍历玩具使用情况，用一个大根堆维护当前玩具下一使用时间
     • 当前玩具如果地上有，直接下一个。
     • 当前玩具地上没有就要从架子上取一个，但在取之前要判断下，地上不同玩具个数是否已经有了 \(k\) 个，如果已满，就把大根堆里的堆顶的物品放回去。

原文：https://www.cnblogs.com/hbhszxyb/p/13403015.html