LeetCode解题报告（326)-- 870. Advantage Shuffle

Problem

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

Note:

1. 1 <= A.length = B.length <= 10000
2. 0 <= A[i] <= 10^9
3. 0 <= B[i] <= 10^9

---

Analysis

  题目给出了两个数组A和B，定义A对B的优势值为A[i] > B[i]的位置数量，题目要求我们通过改变A的顺序使得优势值最大。这样一看，不就是典型的田忌赛马？

  田忌赛马的基本思想就是用恰好强的马去取胜，实在打不过的找个最菜的去应付。换到这道题目中也是一样的，我们只需要找到恰好比B[i]大的数即可，这里的恰好意思是在A中找出最小的满足A[i] > B[i]的值，也就是upper_bound。如果某个对于B[i]，在A中都找不出数比它大，那就是打不过了，找个最小的去应付即可。

---

Solution

  这道题目需要找upper_bound，所以首先需要对A进行排序。然后找upper_bound使用stl的方法即可。

---

Code

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> res;
		multiset<int> st(A.begin(), A.end());
		for (int i = 0; i < B.size(); ++i) {
			auto it = (*st.rbegin() <= B[i]) ? st.begin() : st.upper_bound(B[i]);
			res.push_back(*it);
			st.erase(it);
		}
		return res;
    }
};

---

Summary

  这道题目难度不大，读懂题目意思后，其实就是很典型的田忌赛马问题。然后利用STL提供的方法来求解即可。这道题目的分享到这里，感谢你的支持！