背景
蒟蒻中学高二（1）班遇到了一些小问题。
描述
蒟蒻中学要分班了，大家对老朋友都很依依不舍，高二（1）有n名同学，每个人i都有一个留恋值a[i]，即在被分到新班级之后，还想要和旧班级的至少a[i]名同学在一起（包括自己）。
可蒟蒻中学的老师希望多分几个班，因为小班化的教学可以提高效率。
现在蒟蒻中学希望你写个程序帮助他们来分班，使得在满足所有同学要求的情况下分的班尽可能多。（建议加读入优化，数据保证有解）
输入格式
第一行一个数n，代表有n个学生。
第二行n个数，为每个人的a值，两个数之间用一个空格隔开。
输出格式
一个数，代表分出的最多班数
备注
样例输入
5
1 2 4 3 1
样例输出
2
样例解释
第一个人自己分一个班 其他的人分第二个班
数据范围：
对于30%的数据 1<=n<=30
对于60%的数据 1<=n<=1000
对于100%的数据 1<=n<=1000000
官方题解：
60分做法
首先我们把所有人的a[i]排个序。发现每个组的人大概就是排序后的数列中连续的一段。
感性的认知就是，要求差不多的人在一起。。。
那我们来dp吧！
设f[i]为前i个人的答案 那么f[i]都可以从f[j]转移过来 0<=j<=i-a[i]
暴力N^2可以得60分
100分做法
还是考虑之前那个dp 我们可以记录一个前缀最值s[i]
那么f[i]就可以由s[i-a[i]]转移来
dp方程
f[i]=s[i-a[i]]+1
s[i]=max(s[i-1],f[i])
另一种做法 贪心
首先还是排序 然后从小到大尽量多分组
最后有可能会剩下一些人无法分组 考虑用前面的一组来合并这些人
去掉最后一组 把最后一些人和最后一组的人分为一组
如果还是不行的话 就接着往前合并 因为数据保证有解 最后一定能成功
一种能得20分的错误方法
看到这题好多人都直接想了一种错误的贪心
就是直接排序 从后往前能选多少就选多少
但是很容易就能构造出反例 例如:
1 1 3 3 3 3 3 5 显然答案为两个1各一组 其余人一组 答案为3
而按照那种贪心的话。。。算出来是2。。
评论 (0)
