loj#P2515. 「CEOI2011」Teams

「CEOI2011」Teams

题目描述

nn 个小朋友要进行比赛,他们要被分为若干队伍。每一个小朋友都有一个要求,其中第 ii 个小朋友要求他所在的队伍最少要有 aia_i 个人(包括自己)。
现在请你求出一种划分方案,在满足所有小朋友的要求的情况下,最大化队伍的数量。同时在此基础上,请你最小化人数最多的队伍的人数。

输入格式

第一行一个数 nn 表示小朋友的个数。
接下来 nn 行,每行一个数,其中第 ii 行的数字为 aia_i

输出格式

第一行一个数 tt ,表示在你的方案中的队伍数量。
接下来 tt 行,每行若干个空格隔开的数字,表示一只队伍。每一行首先输出一个数 kik_i 表示第 ii 只队伍的人数,接下来 kik_i 个数依次描述该队伍内的小朋友的编号(从 11 开始)。
若有多解(在满足题目要求的情况下),输出任意一个即可。

5
2
1
2
2
3
2
2 4 2
3 5 1 3

数据范围与提示

对于 50%50\% 的数据,有 n5 000n\le 5\ 000
对于 100%100\% 的数据,有 1n1 000 000;1ain1\le n\le 1\ 000\ 000;1\le a_i\le n,输入保证有解。