JSOI地铁换票 (贪心)

简单贪心即可。

 1 type arr=array[0..10000] of longint;
 2 var a,b:arr;
 3     i,n,m,sum:longint;
 4  procedure sort(var a:arr;l,r: longint);
 5       var
 6          i,j,x,y: longint;
 7       begin
 8          i:=l;
 9          j:=r;
10          x:=a[(l+r) div 2];
11          repeat
12            while a[i]<x do
13             inc(i);
14            while x<a[j] do
15             dec(j);
16            if not(i>j) then
17              begin
18                 y:=a[i];
19                 a[i]:=a[j];
20                 a[j]:=y;
21                 inc(i);
22                 j:=j-1;
23              end;
24          until i>j;
25          if l<j then
26            sort(a,l,j);
27          if i<r then
28            sort(a,i,r);
29       end;
30 begin
31     readln(n,m);
32     for i:=1 to m do readln(a[i],b[i]);
33     sort(a,1,m);
34     sort(b,1,m);
35     sum:=0;
36     for i:=1 to m do sum:=sum+abs(a[i]-b[i]);
37     writeln(sum);
38 
39 end.

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。