604，贪心算法解优势洗牌-田忌赛马问题
问题描述
来源：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 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
问题分析
这题说的是在同一位置如果数组A中的元素大于数组B中的元素，那么数组A就具有一个优势，我们需要对数组A重新排列，让数组A相对于数组B的优势最大。
如果数组的长度是3，这就是经典的田忌赛马问题，大家也都知道该怎么解决。但如果数组的长度不是3，而是100，1000我们该怎么解决呢。这里我们还按照田忌赛马的问题来解决。
数组A我们看作是田忌的马，数组B我们看作是齐王的马，数组中的值表示马跑的快慢。
如果田忌最快的马还没有齐王最快的马跑的快，就用田忌最慢的马和齐王最快的马比赛。
如果田忌最快的马比齐王最快的马跑的快，就用田忌最快的马和齐王最快的马比赛。
因为是一对一的比赛，第一种方案我们都能理解，因为齐王最快的马比田忌最快的马跑的还快（也可以认为比田忌所有的马都快），这时候田忌无论用哪匹马和齐王比赛都会输，既然输，不如用田忌最慢的马和齐王最快的马比赛好了。
对于第二个方案，如果田忌最快的马跑的比齐王最快的马还要快，我们能不能用田忌第二快的马和齐王最快的马比较呢，其实没必要的。
如果田忌第二快的马跑的比齐王最快的马还要快，也就是说田忌最快的前两匹马和齐王的任何一匹马比赛都能获胜，我们就用田忌最快的马和齐王最快的马比赛就行了。
如果田忌第二快的马没有齐王最快的马跑的快，我们只能用田忌最快的马和齐王最快的马比赛。
所以不管田忌第二快的马有没有齐王最快的马跑的快，当田忌最快的马跑的比齐王最快的马还要快的时候，我们就用田忌最快的马和齐王最快的马比赛就行了。
原理也比较简单，我们来看下代码
public int[] advantageCount(int[] nums1, int[] nums2) {
int length = nums1.length;
int[] res = new int[length];
//先对数组nums1从小到大进行排序
Arrays.sort(nums1);
//对数组nums2从大到小排序，这里使用的是优先队列，也就是最大堆，每次出队
//的都是堆中最大的元素。这里存储的是数组nums2中的元素和元素对应的下标
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
//数组nums2中的元素和元素对应的下标加入到队列中
for (int i = 0; i < length; i++)
pq.add(new int[]{nums2[i], i});
//双指针，分别指向数组nums1中的最小值和最大值。可以类比于田忌跑的
//最慢的马和跑的最快的马
int left = 0;
int right = length - 1;
while (!pq.isEmpty()) {
//队列中存放的是数组nums2中的元素，每次出队的都是堆中最大的值，
//类比齐王每次都拿出剩下的马中最好的马比赛
int[] cur = pq.poll();
int index = cur[1];
int val = cur[0];
//先用nums1中的最大值和nums2中的最大值比较，类似于田忌用最好的马
//和齐王最好的马比较，如果田忌最好的马跑的比齐王最好的马跑的快，
//就用田忌最好的马和齐王最好的马比赛
if (nums1[right] > val) {
res[index] = nums1[right--];
} else {
//如果田忌最好的马没有齐王最好的马跑的快，就用田忌最差的马
//和齐王最好的马比赛
res[index] = nums1[left++];
}
}
return res;
}
田忌赛马的故事
文言文：
齐使者如①梁②，孙膑以刑徒阴见，说齐使。齐使以为奇，窃载与之齐。齐将田忌善而客待之。忌数③与齐诸公子④驰逐⑤重射⑥。孙子⑦见其马足⑧不甚相远⑨，马有上、中、下辈⑩。于是孙子谓田忌曰：“君弟⑪重射，臣能令君胜。”田忌信然⑫之，与王及诸公子逐射千金⑬。及⑭临质⑮，孙子曰：“今以君之下驷⑯与彼上驷，取君上驷与彼中驷，取君中驷与彼下驷。”既⑰驰三辈毕，而田忌一不胜而再胜⑱，卒⑲得王千金。于是忌进孙子于威王。威王问兵法，遂⑳以为师。
翻译：
齐国使者到大梁来，孙膑以刑徒的身份秘密拜见，劝说齐国使者。齐国使者觉得此人是个奇人，就偷偷地把他载回齐国。齐国将军田忌非常赏识他，并且待如上宾。田忌经常与齐国众公子赛马，设重金赌注。孙膑发现他们的马脚力都差不多，马分为上、中、下三等，于是对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和各位公子用千金来赌注。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，用您的上等马对付他们的中等马，用您的中等马对付他们的下等马。”三场比赛结束后，田忌一场败而两场胜，最终赢得齐王的千金赌注。因此田忌把孙膑推荐给齐威王。齐威王向他请教了兵法，于是把他当成老师。
翻译：
1.如：往，到......去
2.梁：魏国的都城
3.数：屡次,多次
4.公子：春秋战国时诸侯不能继承君位的儿子称为公子
5.驰逐：驾马车竞逐
6.重射：下很大赌注赌输赢。射：打赌。
7.这里指战国时齐国人孙膑，是春秋末期著名军事家孙武(著有《孙子兵法》)的后世子孙，生卒年不可考。1972年，从山东临沂银雀山一座西汉墓葬中发现了失传一千多年的《孙膑兵法》
8.马足：指马的足力
9.不甚相远：不是相差的很远
10.辈：类，这里指马的不同等级
11.弟：只管
12.然：认为......是正确的 然之：即以之为然
13.逐射千金：下千金的赌注赌驾马车比赛的输赢
14.及：等到
15.临质：将要比赛的时候。质，评判，这里指比赛。
16.驷：古代驾车，一车四马，同驾一辆车的马叫做驷
17.既：已经。这里指三种等级的马驾车比赛结束
18.一不胜而再胜：一次没能取胜，但是后两次都取得了胜利。再：两次。
19.卒：最后
20.遂:于是。
●
●
●
●