题意：有n个a[i]和b[i]，调整顺序使abs(a[i]-b[i])之和最小，但a[i]<>b[i]。保证所有 Ai各不相同，Bi也各不相同。
30%的数据满足：n <= 104 100%的数据满足：1 <= n <= 105，Ai和Bi均为1到106之间的整数。
思路：可以证明调整范围一定在三个数以内
1 var dp:array[0..110000]of int64; 2 a,b,c:array[0..110000]of longint; 3 n,i:longint; 4 5 function clac(x,y:longint):int64; 6 begin 7 if a[x]=b[y] then exit(1<<60) 8 else exit(abs(a[x]-b[y])); 9 end; 10 11 procedure swap(var x,y:longint); 12 var t:longint; 13 begin 14 t:=x; x:=y; y:=t; 15 end; 16 17 function min(x,y:int64):int64; 18 begin 19 if x<y then exit(x); 20 exit(y); 21 end; 22 23 procedure qsort(l,r:longint); 24 var i,j,mid:longint; 25 begin 26 i:=l; j:=r; mid:=c[(l+r)>>1]; 27 repeat 28 while mid>c[i] do inc(i); 29 while mid<c[j] do dec(j); 30 if i<=j then 31 begin 32 swap(c[i],c[j]); 33 inc(i); dec(j); 34 end; 35 until i>j; 36 if l<j then qsort(l,j); 37 if i<r then qsort(i,r); 38 end; 39 40 begin 41 assign(input,'bzoj1237.in'); reset(input); 42 assign(output,'bzoj1237.out'); rewrite(output); 43 readln(n); 44 for i:=1 to n do read(a[i],b[i]); 45 for i:=1 to n do c[i]:=a[i]; 46 qsort(1,n); 47 for i:=1 to n do a[i]:=c[i]; 48 for i:=1 to n do c[i]:=b[i]; 49 qsort(1,n); 50 for i:=1 to n do b[i]:=c[i]; 51 dp[1]:=clac(1,1); 52 dp[2]:=min(clac(1,2)+clac(2,1),dp[1]+clac(2,2)); 53 for i:=3 to n do 54 begin 55 dp[i]:=1<<60; 56 dp[i]:=min(dp[i],dp[i-1]+clac(i,i)); 57 dp[i]:=min(dp[i],dp[i-2]+clac(i,i-1)+clac(i-1,i)); 58 dp[i]:=min(dp[i],dp[i-3]+clac(i-2,i)+clac(i-1,i-2)+clac(i,i-1)); 59 dp[i]:=min(dp[i],dp[i-3]+clac(i-2,i-1)+clac(i-1,i)+clac(i,i-2)); 60 dp[i]:=min(dp[i],dp[i-3]+clac(i-2,i)+clac(i-1,i-1)+clac(i,i-2)); 61 end; 62 if dp[n]>(1<<59) then writeln(-1) 63 else writeln(dp[n]); 64 close(input); 65 close(output); 66 end.