#P2857. [Ceoi2012]jobs

    ID: 1969 传统题 1000ms 128MiB 尝试: 67 已通过: 21 难度: 4 上传者: 标签>CF1600普及+/提高-二分答案按截止时间排序队列桶排序交换论证鸣谢OimasterSpj程序byliutian

[Ceoi2012]jobs

题目描述

在接下来的 nn 天内,你收到了 mm 个生产请求,每天可能受到多个请求。

原则上来说,第 ii 天收到的生产请求只能在第 ii 天完成,但是实际中,你可以最多推迟 dd 天完成请求,即在第 ii 天到 i+di+d 天内完成都可以;进行生产需要使用一种机器,一台机器一天内可以完成一个生产请求。

你的任务是计算出最少需要的机器台数,使得所有生产都能按要求完成。

输入格式

第一行依次给出三个整数 n,d,mn,d,m,表示总天数、最多允许推迟的天数和请求总数。

第二行 mm 个正整数,第 ii 个正整数 aia_i 表示在第 aia_i 天收到了第 ii 个请求。

数据保证第 n−dn-d 天之后不会收到生产请求。

输出格式

第一行一个正整数,表示最少需要的机器个数。

下面 nn 行给出每天完成的请求编号,每一行以 00 结束。

如果存在多种方案,随意输出一种即可。

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
2
5 1 0
9 4 0
2 10 0
6 12 0
3 7 0
11 8 0
0
0

数据规模与约定

对于 100%100\%​​ 的数据,1≤n≤1051\leq n\leq 10^5,1≤m≤1061\leq m\leq 10^6,0≤d<n0\leq d<n​。​