题目描述

样例

参见原题链接.

算法:贪心

考虑A中任意一个值a,若存在$b0 = min \{ b \in B \mid b < a \} $，则a与b0配对，否则,a与B中最大元素配对.
要证明这一策略的正确性，考虑最优的配对策略:
1. 存在b0,最优解中与a0配对，a与b配对.交换a和a0的配对，其他配对不变;若$b < a$，则$b <= b0 < a$交换后a与b0必然匹配,a0与b间的匹配不会比a0与b0间更差;若$b >= a$，则原最优解中这四个数最多贡献了1个配对，交换后也至少有一个配对，不会比最优解差.
2. 不存在b0.设最优解中与B中最大元素b0配对的数为a0.若$a0 <= b0$，则原最优解中这四个数贡献了0对配对，交换后不会更差;若$a0 > b0 > b$，则交换后同为1对配对.

综上，贪心策略是正确的.同样可以得出，对于B中元素b，找A中大于b的元素的最小值，或者A中最小值的贪心策略也是正确的.下面是这种策略的两种实现.

算法1:

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        std::multiset<int> nums;
        for (auto a : A) {
            nums.insert(a);
        }
        A.clear();
        for (auto b : B) {
            auto iter = nums.lower_bound(b + 1);
            if (iter == nums.end()) {
                iter = nums.begin();
            }
            A.push_back(*iter);
            nums.erase(iter);
        }
        return A;
    }
};

算法2

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        std::vector<std::pair<int, int>> BP;
        BP.reserve(B.size());
        for (int i = 0, is = B.size(); i < is; ++i) {
            BP.emplace_back(B[i], i);
        }
        std::sort(A.begin(), A.end());
        std::sort(BP.begin(), BP.end(), [](const pair<int, int> & p1, const pair<int, int> & p2) {
            return p1.first < p2.first;
        });
        std::vector<int> ret(A.size());
        int l = 0, r = B.size() - 1;
        for (int i = 0, is = A.size(); i < is; ++i) {
            if (A[i] > BP[l].first) {
                ret[BP[l++].second] = A[i];
            } else {
                ret[BP[r--].second] = A[i];
            }
        }
        return ret;
    }
};