题目地址：https://leetcode.com/problems/advantage-shuffle/description/
题目描述：
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；
题目大意
如何安排A的各个数字，使得对于每个位置A[i]>B[i]的情况最多。
解题方法
中国人小时候学过的一个故事，叫做田忌赛马，大家应该都知道的，用自己比对方强一点点的马去战胜对方的马，如果对方的马太强了，那么就用自己的最弱的马去参加比赛。这样做的好处就是我们用自己的弱鸡消耗掉对方的精锐，自己获胜的概率就最大。
使用了双向队列解决这个问题。同样是对A,B进行从小到大的排序，排序时需要保存B中的数字原来在数组中的哪个位置。这样我们对A进行一次遍历，每次出动自己的最弱的马，如果这个马能战胜B中最弱的马，那么就这么使用；如果战胜不了的话，那么就用这个最弱的马去和B中最强的马比赛，这样就干掉了对方的精锐。
时间复杂度是O(nlogn)，空间复杂度是O(n).
代码如下：
class Solution(object):
def advantageCount(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: List[int]
"""
res = [-1] * len(A)
A = collections.deque(sorted(A))
B = collections.deque(sorted((b, i) for i, b in enumerate(B)))
for i in range(len(A)):
a = A.popleft()
b = B[0]
if a > b[0]:
B.popleft()
else:
b = B.pop()
res[b[1]] = a
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
参考资料：
https://leetcode.com/problems/advantage-shuffle/discuss/149932/Python-greedy-sol-with-detailed-comment-Chinese-story:-Tian-Ji's-Horse-race
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发