排座椅seats.pas
【问题描述】
上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了两个会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生对数最少。
【输入格式】seats.in
第一行,有5各用空格隔开的整数,分别是M,N,K,L,D(2<=N,M<=1000,0<=K,L,D<=2000)。
接下来D行,每行有4个用空格隔开的整数,第i行的4个整数Xi,Yi,Pi,Qi,表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。
输入数据保证最优方案的唯一性。
【输出格式】seats.out
第一行包含K个整数,a1a2……aK,表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道,其中ai< ai+1,每两个整数之间用空格隔开(行尾没有空格)。
第二行包含L个整数,b1b2……bk,表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道,其中bi< bi+1,每两个整数之间用空格隔开(行尾没有空格)。
【样例输入】
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
【样例输出】
2
2 4
【问题分析】
我们来看看下面一张表所表示的坐位情况,相同符号表示讲话的一对人。若要是横行要划分一个通道,可以看出可以从1与2,2与3,3与4之间划,那到底选择哪个来划通道,才能使得剩下讲话的人数最少呢?
|
1 |
2 |
3 |
4 |
5 |
1 |
■ |
|
|
|
|
2 |
■ |
※ |
◆ |
★ |
★ |
3 |
|
※ |
◆ |
|
|
4 |
|
▲ |
▲ |
|
|
可以看出应该在2与3之间划分横向的通道,因为2与3之间讲话的人最多,这样可以使用前后相邻讲话的人最少,同时还要注意当划横向通道时,对左右相邻讲话的人来说,没有任何影响,即不减少左右讲话的人数。
由此可以看出,要划分横向通道,则需要按每排讲话人数的由多到少的进行划通道即可;对于纵向通道也是这个道理,需要按列讲话人数的由多到少进行划通道即可。
这样我们就需要处理以下几个问题:
(1)把讲话的人按行或按列来保存,若是行相邻则在行号小的那行上讲话人数增加1,否则在列号小的那列上讲话人数增加1。(num[i, 1]用来表示第i行的讲话人数,num[i, 2]用来表示第i列的讲话人数,code[i, 1]表示第i行的原始编号,code[i, 2]表示第i列的原始编号)
Fillchar(num, sizeof(num), 0);
For i := 1 to d do begin
Readln(x1, y1, x2, y2);
If y1 = y2 then inc(num[min(x1, x2), 1]) else inc(num[min(y1, y2),2]);
End;
For i := 1 to n do code[i, 1] := i;
For i := 1 to m do code[i, 2] := i;
(2)然后再按行和列由多到少分别排序
Qsort(1, n, 1); //最后一个参数是1表示按行的排序
Qsort(1, m, 2); //最后一个参数是2表示按列的排序
Qsort过程如下:
procedure Qsort(l, r, k: longint);
var
i, j, x, m : longint;
begin
i := l; j := r; m := num[(i + j) div 2, k];
repeat
while num[i, k] > m do inc(i);
while num[j, k] < m do dec(j);
if i <= j then begin
x := num[i, k]; num[i, k] := num[j, k]; num[j, k] := x;
x := code[i, k]; code[i, k] := code[j, k]; code[j, k] := x;
inc(i); dec(j);
end;
until i > j;
if i < r then Qsort(i, r, k);
if l < j then Qsort(l, j, k);
end;
(3)要考虑输出的顺序是按行号(或列号)的从小到大输出,而不是按行(列)的人数多少来输出的行(列)号的,所以也还需要处理。
用一个标记数组来表示哪些行要划通道,然后再从第1行开始检查哪些行划通道就输出行号。对于列也是相应的处理
Print(n, k, 1);
Print(m, L, 2);
Print过程为:
Procedure print(t, x, y : longint);
Var
i : longint;
Mark :Array[1..maxN] of Boolean;
Begin
Fillchar(mark, sizeof(mark), false);
For i := 1 to x do mark[code[i, y]] := true;
For i := 1 to t do if mark[i] then write(I, ‘ ‘);
Writeln;
End;