2020牛客寒假算法基础集训营6_A 配对（贪心）

题目大意

题目链接

现在有两个正整数集合， 每个集合n个数， 最大化第k大的 两两配对的和。

分析

具体怎么归纳不好说， 纯手工发现， 分别将前k大的数， 一个集合第i小的和另一个集合第i大的， 配对， 得出k个数最后最小的那个数就是答案。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}
int n, k;
int a[10][N];
int main(){
    n = read(), k = read();
    for (int i = 0; i < n; ++i) a[0][i] = read();
    for (int i = 0; i < n; ++i) a[1][i] = read();
    sort(a[0], a[0] + n, greater<int>());
    sort(a[1], a[1] + n, greater<int>());
    int l = 0, r = k - 1;
    while(r >= 0){ //倒序配对
        a[2][l] = a[0][l] + a[1][r];
        r--;l++;
    }
    sort(a[2], a[2] + k, greater<int>());
    cout << a[2][k - 1] << "\n";
    return 0;
}

恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。