#P18420. Shared Memory Switch
Shared Memory Switch
Shared Memory Switch
标准输入、标准输出。
你的任务是为共享内存交换机设计一个最优算法。
共享内存交换机是网络算法中一种简单而非平凡的缓冲架构。本题中有多个输出队列,所有数据包完全相同。每个到达的数据包都指定了一个输出队列;所有输出队列共享一个容量为 的有限缓冲区。
每秒结束时,每个非空队列各发送一个数据包。当缓冲区溢出时,你的算法必须决定丢弃哪个数据包。目标是使最终发送的数据包总数最多,也就是使丢弃的数据包尽量少。
给定 个事件,格式如下:
-1:经过一秒。- 整数 ():一个数据包到达第 个队列。
可以认为,输入事件结束后,缓冲区中剩余的数据包也都会发送出去;等价地,输入末尾还有无限多个 -1 事件。
输入格式
第一行两个非负整数 (),分别为事件数量和交换机的共享缓冲区容量。
第二行包含上述格式的 个事件。
输出格式
第一行输出一个整数,表示最多能发送多少个数据包。
第二行输出最终发送的数据包各自对应的原事件编号,从 1 开始。只能输出到包事件的编号,不能输出 -1 事件的编号。这些编号可以按任意顺序输出。
若没有数据包被发送,第一行仍需输出 0,第二行没有编号。 和 均按原定义允许。
样例 1
14 5
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
9
3 6 8 5 10 4 12 14 2
样例 2
14 4
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
8
3 6 8 5 10 4 12 14