首页 › 题库 › C/C++编程考级 › C/C++编程二级 › 简答题
简答题 偏难
#7542

排课 排课是个世界难题。 假设每个学期有 N 个教学班的课需要排,每周有 M 个时间段可以上课,全校共有 K 间教室,不同排课组合方案的个数可能会超过整个宇宙的…

排课

排课是个世界难题。

假设每个学期有 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.
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//C语言参考题解 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt;   //存储教师信息 struct kb { int L, T[50], time, room; } k[10001];   int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }   int main() { int N, M, K,all=0; scanf("%d %d %d", &amp;N, &amp;M, &amp;K); for (int i = 0; i &lt; N; i++) { scanf("%d", &amp;k[i].L); int flag=0,flagg=0; for (int j = 0; j &lt; k[i].L; j++) scanf("%d", &amp;k[i].T[j]); scanf("%d %d", &amp;k[i].time, &amp;k[i].room); qsort(k[i].T, k[i].L, sizeof(k[0].T[0]), cmp);//每次读入一个教师的不能上课时间段数组之后就排个序,方便用bsearch查找 if (i) { for (int m = 0; m &lt; i; m++) { if (k[i].room == k[m].room &amp;&amp; k[m].time == k[i].time) {//校验是否存在教室冲突 printf("ERROR: Conflict between %d and %d.\n", i+1, m+1); flag=1; all=1; } } } if(bsearch(&amp;k[i].time,k[i].T,k[i].L,sizeof(k[0].T[0]),cmp)){//校验是否存在时间冲突 printf("ERROR: Conflict with instructor for %d.\n",i+1); flagg=1; all=1; } if(flag || flagg){//必须先将两个条件都检验一遍才能初始化 k[i].time=-1*i; k[i].room=-1*i; } } if(!all) printf("Perfect Arrangement for %d classes!",N); }</pre><p><br/></p>
这道题暂未补解析。