[蓝桥杯][历届试题 PREV-53]分考场(Java)
历届试题 分考场
时间限制:1.0s 内存限制:256.0MB
问题描述
n个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入格式
第一行,一个整数n(1<n<100),表示参加考试的人数。
第二行,一个整数m,表示接下来有m行数据
以下m行每行的格式为:两个整数a,b,用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
一行一个整数,表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5
先说说我的错误点:
①因为刚刚做过合根植物,所以先想到的是并查集,结果写着写着发现有问题(1、2认识,1、3认识,但是2、3不认识)
②一直追求边输入边计算,认为这样速度会更快。导致最后数据间相互干扰。
③没想到相互不认识的考生放置在不同考场,还能让考场数量更小。
例如:13认识,24认识,34认识,
按照1234的顺序,一个一个分考场
1 | 2 |
3 | |
4 |
按照1234的顺序,回溯法分考场
1 | 4 |
2 | 3 |
解题思路: 先建一个boolean类型二维数组存储考生间的关系;再建一个int二维数组存储考场与考生之间的关系。回溯法将1、2、3……考生放置考场中(因为要计算最小考场数量),其他也没什么了
java代码:
import java.util.Scanner;
public class Main {
static boolean[][] know;//是否熟悉
static int[][] examRoom;//考场安排
static int res = 101,n;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
know = new boolean[n+1][n+1];
examRoom = new int[n][n+1];
int m = cin.nextInt();
for(int i=0;i<m;i++) {
int a = cin.nextInt();
int b = cin.nextInt();
know[a][b]=know[b][a]=true;
}
dfs(1,0);
System.out.println(res);
cin.close();
}
static void dfs(int examineeId,int examRoomAmo) {
//考场的数量大于或等于出现过的最小的考场数量,别看了,再弄也大了
if(examRoomAmo>=res) return ;
//当我们的考生编号大于考生人数,所有考生都安排好了
if(examineeId>n) {
res = Math.min(res, examRoomAmo);//这时候记录最小的考场数量
return;
}
A:for(int i=0;i<examRoomAmo;i++) { //遍历已经开辟的每个考场
int examineeAmo = examRoom[i][n];//当前考场的最后一位存放当前考场的考生数量
int j;
for(j=0;j<examineeAmo;j++) { //遍历当前考场中每个考生,判断是否认识
if(know[examRoom[i][j]][examineeId]) {//如果两个考生认识
continue A; //跳到下一个考场
}
}
if(j==examineeAmo){
//当前考场的考生与我们的考生都不认识,把我们的考生加入当前考场
examRoom[i][examRoom[i][n]++] = examineeId;
//dfs判断下一个考生放在哪个考场
dfs(examineeId+1,examRoomAmo);
//消除我们上一步的dfs对这次造成影响
examRoom[i][n]--;
}
}
//前边每个考场都认识,新建考场
//把我们的考生放在新考场的第一个位置,新考场考生数量+1
examRoom[examRoomAmo][examRoom[examRoomAmo][n]++] = examineeId;
dfs(examineeId+1,examRoomAmo+1);//dfs下一个考生
--examRoom[examRoomAmo][n];//消除影响
}
}
测试截图: