奶牛卧室_待解决
<center>
提交: 63 解决: 18
[提交][状态][讨论版] </center>
问题 D: 奶牛卧室
时间限制: 1 Sec 内存限制: 128 MB提交: 63 解决: 18
[提交][状态][讨论版] </center>
题目描述
奶牛们有一个习惯，那就是根据自己的编号选择床号。如果一头奶牛编号是a，并且有0..k-1一共k张床，那么她就会选择a mod k号床作为她睡觉的地点。显然，2头牛不能睡在一张床上。那么给出一些奶牛的编号，请你为她们准备一间卧室，使得里面的床的个数最少。
输入
第一行是奶牛的个数n(1<=n<=5000)；第2到第n+1行是每头奶牛的编号Si(1<=Si<=1000000)。
输出
仅一行，是最少的床的数目。
样例输入
5
4
6
9
10
13
样例输出
8
此代码超时！先记下来，回头再看。
代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int cc[1000000]={0}; int main() { int n; int b; int y=0; int sum=0; int a[5005]; int maxx=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } b=n; while(1){ y=0; for(int i=0;i<n;i++){ int ab=a[i]%b; cc[ab]++; if(cc[ab]>=2){ y=1; break; } } if(y==1){ b++; memset(cc,0,b*sizeof(int)); }else{ printf("%d",b); return 0; } } printf("%d",sum); return 0; }
