2018.02.02【GDOI2018】模拟C组—

2018.02.02【GDOI2018】模拟C组——最大配对

本文主要是介绍2018.02.02【GDOI2018】模拟C组——最大配对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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。

思路

首先要将数组a、b进行排序，a数组由小到大，b数组由大到小。然后用指针i=1,j=n,比较元素差的绝对值，选大的就行了。

程序

varn,k,ans:int64;a,b:array[0..100001]of longint;procedure qsort(l,r:longint);
vari,j,mid:longint;
beginif l>=r then exit;i:=l; j:=r;mid:=a[(i+j)div 2];repeatwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegina[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];inc(i); dec(j);end;until i>j;qsort(l,j);qsort(i,r);
end;procedure qsort1(l,r:longint);
vari,j,mid:longint;
beginif l>=r then exit;i:=l; j:=r;mid:=b[(i+j)div 2];repeatwhile b[i]>mid do inc(i);while b[j]<mid do dec(j);if i<=j thenbeginb[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];inc(i); dec(j);end;until i>j;qsort1(l,j);qsort1(i,r);
end;procedure init;
var i:longint;
beginreadln(n,k);for i:=1 to n doread(a[i]);readln;qsort(1,n);for i:=1 to n doread(b[i]);readln;qsort1(1,n);
end;procedure main;
var i,j:longint;
begini:=1; j:=n;while k>0 dobeginif abs(a[i]-b[i])>abs(a[j]-b[j]) thenbeginans:=ans+abs(a[i]-b[i]);inc(i);endelsebeginans:=ans+abs(a[j]-b[j]);dec(j);end;dec(k);end;
end;
begininit;main;writeln(ans);
end.