題目描述
上課的時候總會有一些同學和前后左右的人交頭接耳，這是令小學班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當同學們的座次確定下來之后，只有有限的D對同學上課時會交頭接耳。同學們在教室中坐成了M行N列，坐在第i行第j列的同學的位置是（i,j），為了方便同學們進出，在教室中設(shè)置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個辦法，或許可以減少上課時學生交頭接耳的問題：她打算重新擺放桌椅，改變同學們桌椅間通道的位置，因為如果一條通道隔開了兩個會交頭接耳的同學，那么他們就不會交頭接耳了。請你幫忙給小雪編寫一個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學生的對數(shù)最少。輸入格式：
輸入文件seat.in的第一行，有5個用空格隔開的整數(shù)，分別是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。接下來的D行，每行有4個用空格隔開的整數(shù)。第i行的4個整數(shù)Xi，Yi，Pi，Qi，表示坐在位置(Xi，Yi)與(Pi，Qi)的兩個同學會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。輸入數(shù)據(jù)保證最優(yōu)方案的唯一性。輸出格式：
輸出文件seat.out共兩行。第一行包含K個整數(shù)，a1，a2……aK，表示第a1行和a1+1行之間、第a2行和a2+1行之間、…、第aK行和第aK+1行之間要開辟通道，其中ai< ai+1，每兩個整數(shù)之間用空格隔開（行尾沒有空格）。第二行包含L個整數(shù)，b1，b2……bL，表示第b1列和b1+1列之間、第b2列和b2+1列之間、…、第bL列和第bL+1列之間要開辟通道，其中bi< bi+1，每兩個整數(shù)之間用空格隔開（列尾沒有空格）。題解：
使用結(jié)構(gòu)體標記x,y軸，然后在讀入每一對同學時，如果他們x軸相同就放在一個組，y軸相同放在另一個組，然后把對應(yīng)的數(shù)組的值+1。（對于x軸和y軸，某一條無論怎么分割對其他的分割線都沒有影響。）然后對讀入后這兩個結(jié)構(gòu)體的值降序排序，取前k和前l(fā)個的位置坐標輸出即可，可以證明這是最優(yōu)的思路。代碼：
var s,d,f,g,h,j,z:longint; a:array[1..3000,1..5] of integer; a1:array[1..3000,1..5] of integer; m,n,k,l,i:integer;begin read(m,n,k,l,i); z:=0; j:=0; for s:=1 to i do begin read(d,f,g,h); if d=g then begin z:=z+1; if f<h then begin a[z,1]:=f; a[z,2]:=h; a[z,5]:=d; end else begin a[z,1]:=h; a[z,2]:=f; a[z,5]:=d end; end; if f=h then begin j:=j+1; if d<g then begin a1[j,1]:=d; a1[j,2]:=g; a1[j,5]:=f; end else begin a1[j,1]:=g; a1[j,2]:=d; a1[j,5]:=f; end; end; end; for s:=1 to j do if a1[s,3]=0 then begin a1[s,3]:=1; a1[s,4]:=a1[s,4]+1; for d:=s+1 to j do if (a1[s,1]=a1[d,1]) and (a1[s,2]=a1[d,2]) then begin a1[d,3]:=1; a1[s,4]:=a1[s,4]+1; end; end; for s:=1 to j-1 do for d:=s+1 to j do if a1[s,4]<a1[d,4] then for f:=1 to 5 do begin g:=a1[s,f]; a1[s,f]:=a1[d,f]; a1[d,f]:=g; end; for s:=1 to k-1 do for d:=s+1 to k do if a1[s,1]>a1[d,1] then for f:=1 to 5 do begin g:=a1[s,f]; a1[s,f]:=a1[d,f]; a1[d,f]:=g; end; for s:=1 to k do write(a1[s,1],' '); writeln; for s:=1 to z do if a[s,3]=0 then begin a[s,3]:=1; a[s,4]:=a[s,4]+1; for d:=s+1 to z do if (a[s,1]=a[d,1]) and (a[s,2]=a[d,2]) then begin a[d,3]:=1; a[s,4]:=a[s,4]+1; end; end; for s:=1 to z-1 do for d:=s+1 to z do if a[s,4]<a[d,4] then for f:=1 to 5 do begin g:=a[s,f]; a[s,f]:=a[d,f]; a[d,f]:=g; end; for s:=1 to l-1 do for d:=s+1 to l do if a[s,1]>a[d,1] then for f:=1 to 5 do begin g:=a[s,f]; a[s,f]:=a[d,f]; a[d,f]:=g; end; for s:=1 to l do write(a[s,1],' ');end.新聞熱點
疑難解答
