游客 注册 | 登录
中文 | En

2479 - 换寝室

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 64 MB

换寝室是大家都不愿意碰到的事情，不幸的是，可怜的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?&amp;method=showdetail&amp;id=1059">http://acm.njupt.edu.cn/acmhome/problemdetail.do?&amp;method=showdetail&amp;id=1059</a></span><span>&nbsp;</span>
</p>
<p class="MsoNormal" style="text-indent:22.0pt;">
	<span>该测试数据更大，</span>容易超时，需要设计更好的算法。
</p>


<br />

题目输入

输入第一行是同学的个数n(1<=n<=5,000)；第2到第n+1行是每个同学的学号Si(1<=Si<=1,000,000).

题目输出

输出就是是最少的床的数目。

输入/输出样例

输入格式

5
4
6
9
10
13

输出格式

8

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;
}

Java解答

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner  scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n];
		int max = -1 ; 
		for(int i = 0 ; i < n ; i++) {
			arr[i] = scanner.nextInt();
			if(max < arr[i]) {
				max = arr[i];
			}
		}
		findMinNumber(arr, max);
		scanner.close();
	}

	private static void findMinNumber(int[] arr, int maxNumber) {
		boolean[] visited = new boolean[maxNumber];
		arrangePosition(arr, visited, arr.length);
	}

	private static void arrangePosition(int[] arr, boolean[] visited, int min) {
		
		for(int i = 0 ; i < arr.length ; i ++) {
			int temp = arr[i] % min;
			if(visited[temp]) {
				Arrays.fill(visited, false);
				arrangePosition(arr, visited, min+1);
				return;
			} else {
				visited[temp] = true;
			}
		}
		
		System.out.println(min);
	}

}
请先登陆