UC知道程序题目理解
来源：百度知道 编辑：UC知道 时间：2024/09/24 20:33:50
奶牛们有一个习惯，那就是根据自己的编号选择床号。如果一头奶牛编号是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
我看不懂输出数据是怎么算出来，谁能帮帮忙
有思路也可以提提
输入
第一行是奶牛的个数n(1<=n<=5000)；第2到第n+1行是每头奶牛的编号Si(1<=Si<=1000000)。
输出
仅一行，是最少的床的数目。
样例
BED.IN
5
4
6
9
10
13
BED.OUT
8
我看不懂输出数据是怎么算出来，谁能帮帮忙
有思路也可以提提
计算任意两个号码的差，设为d，那么d和所有d的约数作为床的个数肯定是不行的，因为两个数相差d，那么他们对d或d的约束取模的结果肯定是相同的。在找出了所有的不行的床数后，看自然数中第一个不在这些之列的数是多少，就是答案了
上述中：
4，6的差2，所以排除2，1
4，9的差5，所以排除5，1
4，10的差6，所以排除6，3，2，1
4，13的差9，所以排除9，3，1
6，9的差3，所以排除3，1
6，10的差4，所以排除4，2，1
6，13的差7，所以排除7，1
9，10的差1，所以排除1
9，13的差4，所以排除4，2，1
10，13的差3，所以排除3，1
上面讲的很麻烦，写程序的话也有不少可以优化的地方。比如5头牛，那么5以下的肯定是不够的。另外，也可以把所有差先算出来，再算约束，这样就不必重复计算约束了，等等。。