5801. 消灭怪物的最大数量—分析不能用二分搜索原因-一一网

5801. 消灭怪物的最大数量 – 力扣（LeetCode） (leetcode-cn.com)

这道题一开始就从直觉上锁定了两种方法：贪心或者二分搜索。

后来脑海中一晃而过一个概念：选定某一分钟min = k时，如果k已经输掉了游戏，那么min = k + 1，k + 2….肯定已经不行。于是就决定用二分搜索来做。整个过程耗了很久，一共3,4个小时可能都有。

用例错了就不停地凭直觉修改，基本上是处于一种没有冷静思考的状态了。当然，跟我忘了“二分搜索”的适用条件也有关系

二分搜索：

public class Solution1 {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int[] time = new int[dist.length];

        for (int i = 0; i < dist.length; i++) {
            time[i] = dist[i] / speed[i];
        }
        int max = time[0];
        for (int i = 1; i < dist.length; i++) {
            max = Math.max(max, time[i]);
        }
        int left = 0, right = max + 1;
        int result = 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (check(mid, dist, speed)) {
                left = mid + 1;
                result = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return Math.min(result, dist.length);
    }

    private boolean check(int mid, int[] dist, int[] speed) {
        int count = 0;
        int tmpMid = mid;
        for (int i = 0; i < dist.length; i++) {
            int left = dist[i] - (tmpMid * speed[i]);
            if (left <= 0) {
               int firstZero = (int)Math.ceil((double)(dist[i]) / speed[i]);
               if (firstZero == tmpMid) {
                   count++;
               } else {
                   mid--;
                }
            }
        }

         return count <= mid;
    }

    public static void main(String[] args) {
        Solution1 solution = new Solution1();
//        int[] dist = {1, 3, 4};
//        int[] speed = {1, 1, 1};

//
//        int[] dist = {1,1,2,3};
//        int[] speed = {1,1,1,1};

//
//        int[] dist = {3, 2, 4};
//        int[] speed = {5, 3, 2};

        // 这个
//        int[] dist = {4,2,3};
//        int[] speed = {2,1,1};

//        int[] dist =  {3,5,7,4,5};
//        int[] speed = {2,3,6,3,2};

        // 这个
        int[] dist = {5,4,3,3,3};
        int[] speed = {1,1,5,3,1};

//        int[] dist =  {4,2};
//        int[] speed = {5,1};

        // 这个
//        int[] dist =  {3,3,5,7,7};
//        int[] speed = {1,1,4,2,2};
        System.out.println(solution.eliminateMaximum(dist, speed));
    }
}

复制代码

这道题不能用二分搜索的本质原因是：

首先，二分搜索其实就是为了找到一个阈值m，方法就是不停地逼近。其中有两个重要条件：1）假如某个取值k不行的时候，那么k + 1，k + 2…肯定不行。2）

假如某个取值k行的时候，那么k – 1,k – 2,k – 3…肯定行。 // 也可能反过来，k 不可以那么k以下的肯定不可以，k可以那么k以上的肯定可以。

只有这两个特征的才可以用二分。

这道题就是出现在这里：我上面的那个算法的check方法（判断minute = mid时，是否能够存活下来）并不太对。虽然条件1 当minute = mid时不行的话，mid + 1，mid + 2肯定不行，但是条件2不满足。当minute = mid行并不能证明mid – 1，mid – 2也行。反例是dist = {5,4,3,3,3}，speed = {1,1,5,3,1}。

贪心解法：

贪心的策略也很简单，就是看到达时间，哪个怪兽到达时间短就先消灭。因为每分钟只能消灭一个怪兽，所以如果到达时间大于等于该一轮的时间的话就是失败了

public int eliminateMaximum(int[] dist, int[] speed) {
    int[] time = new int[dist.length];
    for (int i = 0; i < time.length; i++) {
        time[i] = (int)Math.ceil((double)(dist[i]) / speed[i]);
    }
    Arrays.sort(time);

    for (int i = 0; i < time.length; i++) {
        if (time[i] > i) {
            continue;
        } else {
            return i;
        }
    }
    return dist.length;
}
复制代码