2479 - 换寝室
换寝室是大家都不愿意碰到的事情，不幸的是，可怜的wwm高中大学都遇到了。
室友们有一个不成文的规定，那就是根据自己的学号选择床号。如果某同学的学号是a，并且有0..k-1一共k张床，那么他就会选择a%k号床作为他睡觉的地点。显然，两个人不能睡在一张床上。那么给出所有同学的学号，请你为他们准备一间卧室，使得里面的床的数量最少。
<br />
<br />
这道题做出来后，请提交到
<p class="MsoNormal" style="text-indent:22.0pt;">
<span><a href="http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1059">http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1059</a></span><span> </span>
</p>
<p class="MsoNormal" style="text-indent:22.0pt;">
<span>该测试数据更大，</span>容易超时，需要设计更好的算法。
</p>
<br />
Input
输入第一行是同学的个数n(1<=n<=5,000)；第2到第n+1行是每个同学的学号Si(1<=Si<=1,000,000).
Output
输出就是是最少的床的数目。
Examples
Input
5 4 6 9 10 13
Output
8
Solution C++
#include<iostream> #include<vector> using namespace std; int main(){ int a;cin>>a; int i,j,k; int sum=a; vector<int>v; for(i=0;i<a;i++){ int b;cin>>b; v.push_back(b); } sum=a; for(i=0;i<v.size();i++){ k=v[i]%sum; for(j=i+1;j<v.size();j++){ if(v[j]%sum==k){ sum++; i=0; } } } cout<<sum<<endl; return 0; }