奶牛卧室_待解决
<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; }