每日一题：贪心算法解优势洗牌-田忌赛马问题

问题描述：

来源：Leetcode第870题

难度：中等

给定两个大小相等的数组A和B，A相对于B的优势可以用满足A[i]>B[i]的索引i的数目 来描述。

返回A的任意排列，使其相对于B的优势最大化。

实例1：

输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]

实例2：

输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

提示：

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

问题分析：

题目意思：在A的某一元素大于B的相同位置的元素 即为一个优势。

若把题中的数组长度定为3 则 是经典的田忌赛马问题。但解决方法都是一样的，可以按田忌赛马的问题来解决。

数组A看作田忌的马，数组B看作齐公的马，数值表示马跑的速度。若我们想让田忌胜过齐公：

1，若田忌跑的最快的马比齐公最快的马跑的快，就用田忌最快的马和齐王最快的马比赛。

2，若田忌最快的马还没有齐王最快的马跑的快，就用田忌最慢的马和齐王最快的 马比赛。

第二种方案很好理解，跑不赢最快的马，就用最慢的马作为“炮灰”与最快的马比赛。

第一种方案如果田忌最快的马跑的比齐王最快的马还要快，我们能不能用田忌第 二快的马和齐王最快的马比较呢，其实没必要的。

1，如果田忌第二快的马跑的比齐王最快的马还要快，也就是说田忌最快的前两匹马 和齐王的任何一匹马比赛都能获胜，我们就用田忌最快的马和齐王最快的马比赛 就行了。

2，如果田忌第二快的马没有齐王最快的马跑的快，我们只能用田忌最快的马和齐王 最快的马比赛。

所以不管田忌第二快的马有没有齐王最快的马跑的快，当田忌最快的马跑的比齐王最快 的马还要快的时候，我们就用田忌最快的马和齐王最快的马比赛就行了。

详细代码如下：

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) 
    {
        int len=nums1.size();
        vector<int> res(len,0);
        //容器v 用来存储nums2的原始数组元素以及元素下标
        vector<pair<int,int>> v(len);
        for(int i=0;i<len;i++)
        {
            v[i]={nums2[i],i};
        }
        //对nums1 进行从大的到小排序 ，这里使用的是优先队列，也就是最大堆，每次出队
        //的都是堆中最大的元素。
        //对V（nums2）进行从小到大排序
        sort(nums1.begin(),nums1.end(),greater<int>());
        sort(v.begin(),v.end());
        //双指针，分别指向nums1 的最大值 和最小值。可以类比于田忌跑的
        //最慢的马和跑的最快的马 
        int left=0,right=len-1;
        for(int i=len-1;i>=0;i--)
        {
            int val=v[i].first;
            int index=v[i].second;
            //用nums1 的最大值和nums2（v)的最大值比较 即田忌最好的马和齐公最好的马比赛
            if(nums1[left]>val)
            {
                //如果田忌最好的马跑的比齐王最好的马跑的快，
                //就用田忌最好的马和齐王最好的马比赛
                res[index]=nums1[left];
                left++;
            }
            else
            {
                //如果田忌最好的马没有齐王最好的马跑的快，就用田忌最差的马
                //和齐王最好的马比赛
                res[index]=nums1[right];
                right--;
            }
        }
        return res;
    }
};

同时，由于最终结果要与原始的nums2的顺序对应，所以需要用 v存储 nums2 的原始数据以及下标。