pascal 田忌赛马问题

Question

【问题描述】
齐国的将军田忌经常同齐威王赛马。他们赛马的规矩是：双方各下赌注，比赛共设三局，两胜以上为赢家。然而每次比赛田忌总是输家。
但用了孙膑之后，田忌每次都赢。
然而事后齐威王知道了孙膑助阵的事，于是大为不爽。他找来田忌要求重新赛马。为了防止田忌再次cheat，他将孙膑流放到了福州三中实验楼的五楼去刷厕所。然后他重新制订了比赛的规则：对于每匹马由一个速度值。但两匹马比赛时，速度值大的一方会获胜，胜的一方赢1两黄金，输的一方赔一两黄金。如果两马匹的速度值相同，则为平局，双方都不赚不赔。当然，同一匹只能比赛一次。
聪明的孙膑即使是再刷厕所，仍然知道齐威王和田忌两人的所有马的速度值。于是，他忍着双腿的疼痛，爬上了六楼，找到了正在读题的你，并把田忌的最优策略告诉了你，希望你去告诉田忌，但是你做的是一道很菜的题，一是高兴就会忘了田忌的最优策略。于是你只得自己求出田忌的最优策略，并求出田忌最多能赢多上钱。
【输入文件】
第一行：一个整数N，表示双方各有N匹马
第二行：N个正整数，分别表示齐威王每匹马的速度值
第三行：N个正整数，分别表示田忌每匹马的速度值。
【输出文件】
只有一个整数，表示田忌最多能赢多少两黄金。
【样例输入】
3
2 4 6
1 3 5
【样例输出】
1
数据范围
N<=5000
0<=速度值<=500

Answer 1

type
arr=array[1..5000] of integer;
var
a:array[1..2] of arr;
i,j,n,p,l,r,k:integer;
procedure qsort(var a:arr;l,r:integer);
var
i,j,x,y:integer;
begin
i:=l; j:=r; x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j
then begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(a,i,r);
if l<j then qsort(a,l,j);
end;
procedure find;
var
ii,iii:integer;
begin
while (p>=1)and(a[1][p]>=a[2][i]) do
p:=p-1;
if a[1][p]=a[2][i] then
for ii:=p-1 downto 1 do
if a[2][i]>a[1][ii] then begin
for iii:=ii to p do a[1][ii]:=a[1][ii+1]; p:=p-1; end;
end;
begin
readln(n);
p:=n;
for i:=1 to 2 do
begin
for j:=1 to n do
read(a[i][j]);
readln;
end;
qsort(a[1],1,n);
qsort(a[2],1,n);
for i:=n downto 1 do
begin
find;
if p>0 then k:=k+1
else break;
p:=p-1;
end;
writeln(k*2-n);
end.