首先想到费用流，但m<=100000还是算了吧
那就感觉要用dp了，首先将a，b排序
贪心一下可知，a,b的配对肯定不可能出现交叉
这样就可以dp了，复杂度O(nm)还是过不去
在贪心一下会发现，对于a[i],它只可能在j的左右n的范围内匹配(b[j]是b序列中第一个大于a[i]的）
这样就O(n2)了
1 type list=array[0..1000010] of longint; 2 var f:array[0..1,0..1000010] of longint; 3 c,a,b:list; 4 ans,p,k,i,j,l,r,s,e,n,m:longint; 5 6 function min(a,b:longint):longint; 7 begin 8 if a>b then exit(b) else exit(a); 9 end; 10 11 function max(a,b:longint):longint; 12 begin 13 if a>b then exit(a) else exit(b); 14 end; 15 16 procedure qsort(var a :list;m:longint); 17 procedure sort(l,r: longint); 18 var i,j,x,y: longint; 19 begin 20 i:=l; 21 j:=r; 22 x:=a[(l+r) div 2]; 23 repeat 24 while a[i]<x do inc(i); 25 while x<a[j] do dec(j); 26 if not(i>j) then 27 begin 28 y:=a[i]; 29 a[i]:=a[j]; 30 a[j]:=y; 31 inc(i); 32 j:=j-1; 33 end; 34 until i>j; 35 if l<j then sort(l,j); 36 if i<r then sort(i,r); 37 end; 38 39 begin 40 sort(1,m); 41 end; 42 43 begin 44 readln(m,n); 45 for i:=1 to m do 46 readln(b[i]); 47 for i:=1 to n do 48 readln(a[i]); 49 qsort(a,n); 50 qsort(b,m); 51 p:=1; 52 for i:=1 to n do 53 begin 54 while (p<=m) and (a[i]>=b[p]) do inc(p); 55 c[i]:=p; 56 end; 57 k:=0; 58 for i:=1 to n do 59 begin 60 k:=1-k; 61 l:=max(i-1,c[i-1]-n); 62 r:=min(m,c[i-1]+n); 63 s:=max(i,c[i]-n); 64 e:=min(m,c[i]+n); 65 if i=1 then r:=m-n+1; 66 f[k,s-1]:=2147483647; 67 p:=l; 68 for j:=s to e do 69 begin 70 f[k,j]:=f[k,j-1]; 71 while (p<j) and (p<=r) do 72 begin 73 f[k,j]:=min(f[k,j],f[1-k,p]); 74 inc(p); 75 end; 76 end; 77 for j:=s to e do 78 if f[k,j]<>2147483647 then inc(f[k,j],abs(a[i]-b[j])); 79 end; 80 ans:=2147483647; 81 for i:=s to e do 82 ans:=min(ans,f[k,i]); 83 writeln(ans); 84 end.