【3.5】贪心算法-解优势洗牌(类田忌赛马问题)

一、问题

二、解题思路

        这个问题要求我们重新排列数组A，使得在相同位置上，数组A的元素大于数组B的元素的次数最多，从而最大化数组A相对于数组B的优势。我们可以将数组A视为田忌的马匹，数组B视为齐王的马匹，数组中的数值代表马匹的速度。

        对于任意长度的数组，我们可以采用类似田忌赛马的策略来解决这个问题：

        1. **如果田忌最快的马速度不及齐王最快的马**，那么田忌应该用最慢的马与齐王最快的马比赛。因为齐王最快的马已经超过了田忌最快的马，田忌无论派出哪匹马都会输，所以选择用最慢的马来节省实力。

        2. **如果田忌最快的马速度超过齐王最快的马**，那么田忌应该用最快的马与齐王最快的马比赛。因为田忌最快的马能够赢得这场比赛，所以应该充分利用这匹马的优势。

        这种策略的合理性在于，通过比较田忌和齐王最快的马，我们可以决定是否值得用田忌最快的马去争取胜利。如果田忌最快的马无法胜过齐王最快的马，那么使用最慢的马是明智的选择，因为这样可以保留更强的马匹用于后续的比赛。反之，如果田忌最快的马能够胜过齐王最快的马，那么就应该用它来确保这场比赛的胜利。

        通过这种贪心算法的策略，我们可以在每一步都做出当前最优的选择，从而最大化数组A相对于数组B的优势。

三、代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>std::vector<int> advantageCount(std::vector<int>& nums1, std::vector<int>& nums2) {int length = nums1.size();std::vector<int> res(length);// 先对数组nums1从小到大进行排序std::sort(nums1.begin(), nums1.end());// 对数组nums2从大到小排序，这里使用的是优先队列，也就是最大堆，每次出队的都是堆中最大的元素// 这里存储的是数组nums2中的元素和元素对应的下标std::priority_queue<std::pair<int, int>> pq;for (int i = 0; i < length; i++) {pq.push({nums2[i], i});}// 双指针，分别指向数组nums1中的最小值和最大值。可以类比于田忌跑的最慢的马和跑的最快的马int left = 0;int right = length - 1;while (!pq.empty()) {// 队列中存放的是数组nums2中的元素，每次出队的都是堆中最大的值，// 类比齐王每次都拿出剩下的马中最好的马比赛auto cur = pq.top();pq.pop();int index = cur.second;int val = cur.first;// 先用nums1中的最大值和nums2中的最大值比较，类似于田忌用最好的马// 和齐王最好的马比较，如果田忌最好的马跑的比齐王最好的马跑的快，// 就用田忌最好的马和齐王最好的马比赛if (nums1[right] > val) {res[index] = nums1[right--];} else {// 如果田忌最好的马没有齐王最好的马跑的快，就用田忌最差的马// 和齐王最好的马比赛res[index] = nums1[left++];}}return res;
}int main() {std::vector<int> nums1 = {2, 7, 11, 15};std::vector<int> nums2 = {1, 10, 4, 11};std::vector<int> result = advantageCount(nums1, nums2);for (int num : result) {std::cout << num << " ";}std::cout << std::endl;return 0;
}