问题 25806. -- 【排序】最大配对(Vijos P1662)

25806: 【排序】最大配对(Vijos P1662)

时间限制: 1 Sec  内存限制: 128 MB
献花: 1  解决: 1
[献花][花圈]

题目描述

    给出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序列。

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

输出

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

样例输入

4 2
2 5 6 3
1 4 6 7

样例输出

10

提示


样例说明:配对(2,7)、(6,1)结果为|2-7|+|6-1|=10。



算法分析:先对A,B进行排序(快排),比较(A尾-B头)和(B尾-A头)的大小,取大的,然后一直取直到取满K个。




来源

[献花][花圈]