题解 CF1353B 【Two Arrays And Swaps】
smallfang
2020-05-18 22:55:40
CF1353B 题解
本题呢，我们可以用堆，因为我们要保证a数组最大。那么我们可以搞一个小根堆来搞。一开始把a数组全都push进去。然后将b数组从大到小排序。选前k个。每次将b[i] push到优先队列，然后取出堆顶。k此操作。我们可以使用优先队列实现。
原理为：每次拿出来的一定是最小的，而剩下的一定是和最大的。而我们取着k个数字一定是b中最大的。所以我们可以发现通过上述方法，得到的优先队列里的数的和是最大的。
Code:
```cpp
#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;
}
```