眼睛凹进去了能恢复吗:关于程序设计中的同余问题的解决

来源:百度文库 编辑:杭州交通信息网 时间:2024/07/21 20:51:55
原题目是:
奶牛卧室

奶牛们有一个习惯,那就是根据自己的编号选择床号。如果一头奶牛编号是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的可能性所需要的时间和空间将会很大,超出时间的情况肯定出现。

请问此类同于问题如何减少判断同余的情况?