查人人中国名人网新加坡圣淘沙度假村:关于程序设计中的同余问题的解决
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/29 05:18:41
原题目是：
奶牛卧室
奶牛们有一个习惯，那就是根据自己的编号选择床号。如果一头奶牛编号是a，并且有0..k-1一共k张床，那么她就会选择a mod k号床作为她睡觉的地点。显然，2头牛不能睡在一张床上。那么给出一些奶牛的编号，请你为她们准备一间卧室，使得里面的床的个数最少。
输入
第一行是奶牛的个数n(1<=n<=5000)；第2到第n+1行是每头奶牛的编号Si(1<=Si<=1000000)。
输出
仅一行，是最少的床的数目。
样例
BED.IN
5
4
6
9
10
13
BED.OUT
8
用pascal解决，其中问题的核心是判断同余，但是不断枚举M的可能性所需要的时间和空间将会很大，超出时间的情况肯定出现。
请问此类同于问题如何减少判断同余的情况？
奶牛卧室
奶牛们有一个习惯，那就是根据自己的编号选择床号。如果一头奶牛编号是a，并且有0..k-1一共k张床，那么她就会选择a mod k号床作为她睡觉的地点。显然，2头牛不能睡在一张床上。那么给出一些奶牛的编号，请你为她们准备一间卧室，使得里面的床的个数最少。
输入
第一行是奶牛的个数n(1<=n<=5000)；第2到第n+1行是每头奶牛的编号Si(1<=Si<=1000000)。
输出
仅一行，是最少的床的数目。
样例
BED.IN
5
4
6
9
10
13
BED.OUT
8
用pascal解决，其中问题的核心是判断同余，但是不断枚举M的可能性所需要的时间和空间将会很大，超出时间的情况肯定出现。
请问此类同于问题如何减少判断同余的情况？