最大配对

Description

　　给出2个序列A={a[1]，a[2]，…，a[n]}，B={b[1]，b[2]，…，b[n]}，从A、B中各选出k个元素进行一一配对（可以不按照原来在序列中的顺序），并使得所有配对元素差的绝对值之和最大。
　　例如各选出了a[p[1]]，a[p[2]]，……，a[p[k]]与b[q[1]]，b[q[2]]，……，b[q[k]]，其中p序列中的元素两两不相同，q序列中的元素两两不相同，那么答案为|a[p[1]]－b[q[1]]|＋|a[p[2]]－b[q[2]]|＋……＋|a[p[k]]－b[q[k]]|，现在任务也就是最大化这个答案。

Input

　　输入的第1行为2个正整数n，k，表示了序列的长度和各要选出元素的个数。
　　第2行包含n个正整数，描述了A序列。
　　第3行包含n个正整数，描述了B序列。

Output

　　输出仅包括一个非负整数，为最大的结果。
　　注意：答案可能超过2^31-1，请使用int64或者long long（若使用printf输出请用“%I64d”）类型储存结果。

Sample Input

4 2
2 5 6 3
1 4 6 7

Sample Output

Data Constraint

Hint

【样例说明】
　　配对（2，7）、（6，1）结果为|2-7|+|6-1|=10。
【数据说明】
　　对于10%的数据，有k≤5，n≤10；
　　对于30%的数据，有n≤100；
　　对于50%的数据，有n≤1000；
　　对于100%的数据，有k≤n≤100000；a[i]，b[i]≤1000000。
.
.
.
.
.
.

分析

贪心，排序，累加。
.
.
.
.
.
.

程序：

var
n,k,i,l,r:longint;
ans:int64;
a,b:array[-1..200000]of longint;

procedure kp1(l,r:longint);
var
i,j,mid:longint;
begin
    if l>=r then exit;
    i:=l;j:=r;mid:=a[(i+j) div 2];
    repeat
         while a[i]<mid do inc(i);
         while a[j]>mid do dec(j);
         if i<=j then
         begin
             a[-1]:=a[i];a[i]:=a[j];a[j]:=a[-1];
             inc(i);dec(j);
         end;
    until i>j;
    kp1(l,j);
    kp1(i,r);
end;

procedure kp2(l,r:longint);
var
i,j,mid:longint;
begin
    if l>=r then exit;
    i:=l;j:=r;mid:=b[(i+j) div 2];
    repeat
         while b[i]>mid do inc(i);
         while b[j]<mid do dec(j);
         if i<=j then
         begin
             b[-1]:=b[i];b[i]:=b[j];b[j]:=b[-1];
             inc(i);dec(j);
         end;
    until i>j;
    kp2(l,j);
    kp2(i,r);
end;

begin
    readln(n,k);
    for i:=1 to n do
    read(a[i]);
    readln;
    for i:=1 to n do
    read(b[i]);
    kp1(1,n);
    kp2(1,n);
    l:=1;r:=n;
    ans:=0;
    for i:=1 to k do
    begin
        if l=r then
        begin
            ans:=ans+abs(b[l]-a[l]);
            break;
        end;
        if abs(b[l]-a[l])>=abs(b[r]-a[r]) then
        begin
            ans:=ans+abs(b[l]-a[l]);
            inc(l);
        end else
        begin
            ans:=ans+abs(b[r]-a[r]);
            dec(r);
        end;
    end;
    write(ans);
end.