你好|lintcode 1692. 组队打怪你好|leetcode

你现在有n个英雄，每个英雄的战斗力为atk1,你要用这些英雄去对付n个怪物，每个怪物的战斗力为atk2。在一场战斗中，你需要安排每个英雄分别与一个怪兽战斗，如果英雄战斗力高于怪兽，那个怪兽就会被击杀，问最多能击杀几个怪兽？

给定atk1=[6,4,8,5,1],atk=[2,3,4,5,6]，返回4

解释: * 6>4 * 4>2 * 8>6 * 5>3 * 1<5

注意事项 2<=n,m<=100000

这道题目其实就是田忌赛马的思路

public int getAns(int[] atk1, int[] atk2) {Arrays.sort(atk1); Arrays.sort(atk2); int i = 0, j = 0, x = atk1.length - 1, y = atk2.length - 1, res = 0; boolean isLast = true; while (isLast) { if (x == i) isLast = false; if (atk1[x] > atk2[y]) { //如果最厉害的英雄可以战胜最厉害的怪兽打 x--; y--; res++; } else if (atk1[i] > atk2[j]) {//如果最弱的英雄可以战胜最弱的怪兽打 i++; j++; res++; } else { //如果不行就让最弱的英雄去打最厉害的怪兽 i++; y--; } } return res; }

【你好|lintcode 1692. 组队打怪】