本文主要是介绍NOIP-模拟试题之--分组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2018 NOIP 全套资料下载提取码:072k
【问题描述】
Mr_ he打算把自己棋下的 n 个选手分成若干组。每个选手都提出自己的要求,那就是第 i 个选手要求自己所属的组的人数大等于a[i]人。在满足所有选手的要求的前提下,Mr_he打算最大化组的总数,请你来帮助他!。注意,分组时每个选手属于且仅属于一组。
【输入格式】
第一行一个整数 n, 表示人数。以下 n 行, 每行一个整数表示 a[i]。
【输出格式】
输出队伍总数的最大值。 数据保证有解。
【输入样例】
5
2
1
2
2
3
【输出样例】
2
【数据范围】
对于 20%的数据, n <= 10
对于 40%的数据, n <= 1000
对于 60%的数据, n <= 10000
对于 100%的数据, 1 <= n <= 10^6
————————————————————————————————————————————————————————
可能是出于某种无脑的本能,一开始就想到要贪心去了,实际上最粗暴的贪心很好想就是把需求从大到小排序来直接选人。但是可以被卡掉,比如这组数据:1 1 1 3 4 4 4 4,发现一贪就是3组不巧可以分成4组。
有一种贪心是从小到大排序,然后一直选直到当前满足这组里面所有人的要求为止。出现最后有人分不完的时候就把上一次分组的人合并到这一组里面来&#x
这篇关于NOIP-模拟试题之--分组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!