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