870. Advantage Shuffle
思路
用priority_queue<pair<int, int>>解决。使用贪心算法，按数组A从大到小尽可能在数组B中找到匹配的元素即可。就像是“田忌赛马”一样，让A的上等马去应付B的中等马，依次类推，就能有尽可能多的匹配对数。
技巧度：C, 思维绕脑度：C
贪心算法
代码
typedef pair<int, int> mp;
bool operator <(mp &p1, mp &p2){
return p1.first >= p2.first;
}
class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
priority_queue<mp> q;
vector<int> res(A.size(), 0);
stack<mp> st;
map<int, int> ma;
map<int, int> mb;
sort(A.begin(), A.end(), greater<int>());
for (int i = 0; i < B.size(); i++)
q.push({B[i], i});
for (int i = 0; i < A.size(); i++) {
while(!q.empty() && A[i] <= q.top().first) {
st.push(q.top());
q.pop();
}
if (!q.empty()) {
auto p = q.top();
res[p.second] = A[i];
q.pop();
}
else {
auto p = st.top();
res[p.second] = A[i];
st.pop();
}
}
return res;
}
};
