A29557. 排课
题目描述
排课
题目描述
排课是个世界难题。
假设每个学期有 N 个教学班的课需要排，每周有 M 个时间段可以上课，全校共有 K 间教室，不同排课组合方案的个数可能会超过整个宇宙的质子数。更为复杂的是，每个学期排课前，学校还会收集每个教学班任课老师不能上课的时间段，还要保证排课不与老师的时间安排起冲突。
当然，本题不是要求你实现一个排课算法，而是要求你实现一个排课方案检查算法。即给定每个教学班上课的时间和地点，你需要检查这个时间段和地点是否只有这一个班上课，并且这个上课时间不会正好是任课老师不能上课的时间。
时间限制：5000 内存限制：65536
输入
输入在第一行中给出三个正整数：N（≤ 104）为教学班总数；M（≤ 40）为一周内上课时间段的个数；K（≤ 103）为教室总数。数字间以空格分隔。以下我们就将教学班、时间段、教室分别从 1 开始顺序编号。 随后 N 行，每行给出一个教学班的任课教师时间限制和排课的信息。格式如下： L T[1] ... T[L] Time Room 其中 L 是任课教师的时间限制数量（< M），后面给出 L 个该老师不能上课的时间段编号；Time 是该教学班安排的上课时间段编号，Room 是上课教室编号。
输出
如果给定的课表安排是完全无冲突的，则在一行内输出：Perfect Arrangement for N classes! 其中 N 是教学班数量。 如果课表有冲突，则需要输出冲突原因。我们首先假设教学班是按照编号递增序进行排课的，教学资源先到先得。如果后面安排的教学班 A 跟前面的教学班 B 排在了同一个时间和地点，则在一行中输出 ERROR: Conflict between A and B.；如果教学班 A 的上课时间跟任课教师有冲突，则在一行中输出 ERROR: Conflict with instructor for A.。当两种冲突都发生时，分两行输出，先输出教学班冲突的信息。发生冲突的教学班暂不安排。
样例输入
样例1：
5 20 10
2 1 5 10 7
0 10 3
5 2 4 6 8 10 3 3
3 10 3 18 15 1
1 20 19 10样例2：
5 20 10
2 1 5 10 7
0 10 7
5 2 4 6 8 10 6 3
3 10 3 18 6 3
2 20 10 10 7样例输出
样例1：
Perfect Arrangement for 5 classes!样例2：
ERROR: Conflict between 2 and 1.
ERROR: Conflict with instructor for 3.
ERROR: Conflict between 5 and 1.
ERROR: Conflict with instructor for 5.参考答案
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main() {
int N,M,K;
cin>>N>>M>>K;
int a[N+1][2]; //定义二维数组a，存放每个教学班的有效排课信息
memset(a,0,sizeof(a)); //初始化教学班排课信息为0
int b[300][2]; //定义二维数组b，存放发生冲突的排课信息
int er=0; //冲突数量
for(int i=1;i<=N;i++){ //对输入的N个教学班的排课信息进行循环
int L; //任课教师的时间限制数量
cin>>L;
int T[L]; //数组T存放任课教师不能上课的时间段编号
for(int j=0;j<L;j++){
cin>>T[j];
}
int Time; //Time是该教学班安排的上课时间段编号，
int Room; //Room是上课教室编号
cin>>Time>>Room;
int t1=0; //当前教学班上课时间跟任课教师是否冲突，冲突为1
for(int h=0;h<L;h++){
if(T[h]==Time){
t1=1;
break;
}
}
int n1=0; //当前教学班是否跟前面的教学班有冲突，冲突为前面的教学班编号
for(int g=1;g<=N;g++){
if(Time==a[g][0]&&Room==a[g][1]){
n1=g;
break;
}
}
if(n1!=0){ //如果当前教学班的排课时间和教室与前面的有冲突
b[er][0]=i; //则第1列存入当前教学班的编号
b[er][1]=n1; //第2列存入前面教学班的编号
er++; //冲突数加1
}
if(t1!=0){ //如果当前教学班上课时间跟任课教师有冲突
b[er][0]=0; //则第1列存入0
b[er][1]=i; //第2列存入当前教学班的编号
er++; //冲突数加1
}
if(n1==0&&t1==0){ //如果以上2个条件都没有冲突
a[i][0]=Time; //则修改当前教学班的排课信息为输入的有效信息
a[i][1]=Room;
}
}
if(er==0) printf("Perfect Arrangement for %d classes!",N);
else{
for(int i=0;i<er;i++){
if(b[i][0]==0) printf("ERROR: Conflict with instructor for %d.\n",b[i][1]);
else printf("ERROR: Conflict between %d and %d.\n",b[i][0],b[i][1]);
}
}
return 0;
}