题解 CF1353B 【Two Arrays And Swaps】

CF1353B 题解

本题呢，我们可以用堆，因为我们要保证a数组最大。那么我们可以搞一个小根堆来搞。一开始把a数组全都push进去。然后将b数组从大到小排序。选前k个。每次将b[i] push到优先队列，然后取出堆顶。k此操作。我们可以使用优先队列实现。

原理为：每次拿出来的一定是最小的，而剩下的一定是和最大的。而我们取着k个数字一定是b中最大的。所以我们可以发现通过上述方法，得到的优先队列里的数的和是最大的。

Code:

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m, k;
int a[10001], b[10001];

bool cmp(int x, int y)
{
    return x > y;
}

int main()
{

    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    int t;
    cin >> t;
    while( t -- )
    {
        cin >> n >> m;
        int res = 0;
        priority_queue<int,vector<int> ,greater<int> > q;
        for(int i = 1; i <= n; i ++ )
        {
            cin >> a[i];
            q.push(a[i]);
        }
        for(int i = 1; i <= n; i ++ )
        {
            cin >> b[i];
        }
        sort(b + 1, b + 1 + n, cmp);
        for(int i = 1; i <= m; i ++ )
        {
            q.push(b[i]);
            q.pop();
        }
        while(!q.empty())
        {
            res += q.top();
            q.pop();
        }
        printf("%d\n", res);
    }
    return 0;
}