奶牛们有一个习惯，那就是根据自己的编号选择床号。如果一头奶牛编号是a，并且有0..k-1一共k张床，那么她就会选择a mod k号床作为她睡觉的地点。显然，2头牛不能睡在一张床上。那么给出一些奶牛的编号，请你为她们准备一间卧室，使得里面的床的个数最少。
输入
第一行是奶牛的个数n(1<=n<=5000)；第2到第n+1行是每头奶牛的编号Si(1<=Si<=1000000)。
输出
仅一行，是最少的床的数目。
样例
Input
5
4
6
9
10
13
Output
8
思路：
就是任意两个编号mod k之后的值不能相等，也就是说，任意两个编号之差不能被k整除。
TLE代码：
#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LL long long int int main() { int n; while(~scanf("%d",&n)) { vector<int>vec; int a[5005]; int maxn = -1; for(int i=0; i<n; i++) { scanf("%d",&a[i]); maxn = max(maxn,a[i]); if(i != 0) { for(int j=i-1; j>=0; j--) { vec.push_back(abs(a[i]-a[j])); } } } int len = vec.size(); int j = 0; for(int i=n; i<=maxn; i++) { int flag = 1; for(; j<len; j++) { if(vec[j]%i == 0) { j=0; flag = 0; break; } } if(flag) { printf("%d\n",i); break; } } } return 0; }//FROM CJZ后面的复杂度由于编号情况不确定不好算，是 O(1e6 * 编号差不同的数量)，粗略感觉要超时，尝试交一发，果然超时了。
思路一：
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define LL long long #define PI acos(-1.0) using namespace std; int book[1000005]; int a[5005]; int main() { int n; int maxn = -1; scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d",&a[i]); maxn = max(maxn,a[i]); if(i != 0) { for(int j=i-1; j>=0; j--) { book[abs(a[i]-a[j])] = 1; } } } for(int i=n; i<=maxn; i++) { int t = i; int flag = 1; while(t <= maxn) { if(book[t] == 1) { flag = 0; break; } t += i; } if(flag == 1) { printf("%d\n",i); break; } } return 0; }//FROM CJZ 这个代码思路看起来和第一个超时代码差不多，但其实是1.5*1e7+4*1e7 = O(5.5*1e7),并不会超时。原因是后面的复杂度从第1e6/n + 1e6/(n+1) + 1e6/(n+2) +……+ 1e6/1e6 = 4*1e7。
