Problem Description

Xuejiejie is a beautiful and charming sharpshooter.

She often carries guns, and every gun has an attack power .

One day, Xuejiejie goes outside and comes across monsters, and every monster has a defensive power .

Xuejiejie can use the gun to kill the monster , which satisfies , and then she will get bonus .

Remember that every gun can be used to kill at most one monster, and obviously every monster can be killed at most once. Xuejiejie wants to gain most of the bonus. It's no need for her to kill all monsters.

Input

In the first line there is an integer , indicates the number of test cases.

In each case:

The first line contains two integers , .

The second line contains integers, which means every gun's attack power.

The third line contains integers, which mean every monster's defensive power.

Output

For each test case, output one integer which means the maximum of the bonus Xuejiejie could gain.

薛杰杰这个名字好好听，一听就是拿着枪（扛枪）战斗力爆表的美女 斯哈斯哈

#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=100001;
//自定义降序函数
bool Compare(int x,int y)
{
    return x>y;
}

int main()
{
    int T;
    long long m,n;
    long long a[MAXN],b[MAXN];
    while(scanf("%lld",&T)!=EOF)
    {
        //输入m n
        cin>>m>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int j=0;j<m;j++)
            cin>>b[j];
        //排序 将a[i]按降序排列 最大值在前
        //将b[j]按升序排列
        sort(a,a+n,Compare);
        sort(b,b+m);
        //此时的a b数组均排序成功
        long long result=0;//总奖金
        for(int i=0;i<n;i++)
        {
            if(a[i]<=b[i] || i>=m)//当此时会退出，第一种情况是 怪兽都被打爆
                //第二种是枪的战斗力不及怪兽的能力，为什么会直接break呢？因为都是按照顺序排序，如果打不过这个怪兽，之后的怪兽会更厉害，会更打不过，于是直接跳出循环
                break;
            result+=a[i]-b[i];
        }

        printf("%lld",result);

    }

    return 0;
}

思路：

需要在a[i]>b[j]的情况下,使a[i]尽可能大，而b[j]尽可能小。贪心策略为用当前剩下的枪去打最弱的怪物，以便让每一枪都能获得当前情况下最大的奖金。

** 数据类型longlong

** 枪的数量，和怪物的数量，不一定是相等的，所以我们这里要特殊处理一下。