LintCode 1692. 组队打怪（田忌赛马，二分查找）

1. 题目

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

样例 1:
输入: atk1 = [6, 4, 8, 5, 1], atk2 = [2, 3, 4, 5, 6]
Output: 4
解释:
6 > 4
4 > 2
8 > 6
5 > 3
1 < 5

样例 2:
输入: atk1 =[43,25,33,17], atk2 = [41,41,17,11]
Output: 3
解释:
42 > 41
33 > 17
25> 11
17 < 41

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

2. 解题

• 对怪兽 atk2 进行排序

• 遍历每个英雄，去二分查找比我小的最后一个怪兽（我能力下，能打败的最强的怪兽）

• 变形版 二分查找请参考

class Solution {
public:
    int getAns(vector<int> &atk1, vector<int> &atk2) {
        //sort(atk1.begin(),atk1.end());
        sort(atk2.begin(),atk2.end());
        int i = 0, j = 0, count = 0;
        for(i = 0; i < atk1.size(); ++i)
        {
        	j = bs(atk2,atk1[i],0,atk2.size()-1);
        	if(j == -1)//没找到能打赢的
        		atk2.pop_back();//输给最强的吧，拉低怪兽的实力
        	else
        	{
        		count++;//能打赢，不能打个菜鸟吧，找个最强的
        		atk2.erase(atk2.begin()+j);
        	}
        }
        return count;
    }

    int bs(vector<int>& a, int &target, int l, int r)
    {	//二分查找小于 target 的最后一个
    	int mid;
    	while(l <= r)
    	{
    	    mid = l+((r-l)>>1);
    		if(a[mid] >= target)
    			r = mid-1;
    		else
    		{
    			if((mid==a.size()-1) || a[mid+1] >= target)
    				return mid;
    			else
    				l = mid+1;
    		}
    	}
    	return -1;
    }
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39

• 数组 erase 操作，数据搬移，很耗费时间，有更好的解法吗？求指教。

100% 数据通过测试
总耗时 855 ms
您的提交打败了 1.39% 的提交!