11
3
2015
0

【tyvj月赛】【dp】【贪心】班级分配

背景

蒟蒻中学高二(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。。

Category: 贪心 | Tags: | Read Count: 196

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com