noip 竞赛freepascal2008复赛题目"排座位"

来源:百度知道 编辑:UC知道 时间:2024/06/23 21:10:16

用的是赛前集训时提到的贪心,当时说某些题目用贪心可以得部分分,但是本题贪心可以得满分的。
当然本题的贪心需要预处理下,开2个一维数组,row[i]录如果在第i行加通道,可以分割多少对调皮学生,col[i]记录如果在第j列加通道,可以分割多少对调皮学生,最后贪心法输出分割学生最多的前K行和前L列。
参考程序:
program seat;
const
inp='seat.in';
oup='seat.out';

var
flag,m,n,k,l,d,i,j,x,y,x1,y1:longint;
tmp,col,row:array[1..1000] of longint;
s,s1:ansistring;
procedure flink;
begin
assign(input,inp);
reset(input);
assign(output,oup);
rewrite(output);
end;
procedure fclose;
begin
close(input);
close(output);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a); exit(b);
end;
procedure qsort(m,n:Longint);//快排
var
i,j,k,t:longint;
begin
i:=m; j:=n; k:=tmp[(i+j) shr 1];
repeat
while tmp[i]>k do inc(i);
while tmp[j]<k do dec(j);
if i<=j the