/ Vijos / 题库 /

最大配对

最大配对

背景

Orz5-1 match

描述

给出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]]|,现在任务也就是最大化这个答案。

格式

输入格式

输入的第1行为2个正整数n,k,表示了序列的长度和各要选出元素的个数。

第2行包含n个正整数,描述了A序列。

第3行包含n个正整数,描述了B序列。

输出格式

输出仅包括一个非负整数,为最大的结果。

注意:答案可能超过2^31-1,请使用int64或者long long(若使用printf输出请用“%I64d”)类型储存结果。

样例1

样例输入1

4 2
2 5 6 3
1 4 6 7

样例输出1

10

限制

对于10%的数据,有k≤5,n≤10;
对于30%的数据,有n≤100;
对于50%的数据,有n≤1000;
对于100%的数据,有k≤n≤100000;a[i],b[i]≤1000000。

时限1s。

提示

配对(2,7)、(6,1)结果为|2-7|+|6-1|=10。

信息

ID
1662
难度
4
分类
贪心 点击显示
标签
(无)
递交数
2276
已通过
932
通过率
41%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Orz教主第五次模拟赛