5801. Maximum number of monsters destroyed – LeetCode (leetcode-cn.com)

This problem starts with an intuitive focus on two approaches: greedy or binary search.

Then a concept came to mind: select a minute when min = k and if K has already lost the game, min = K + 1 and k + 2…. Certainly not anymore. So I decided to use binary search. It took a long time, maybe three or four hours.

Use cases that are wrong are constantly modified by intuition, basically in a state of dispassion. Of course, it has something to do with the fact that I forgot how binary search works

Binary search:

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};

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

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

        / / this
        int[] dist = {5.4.3.3.3};
        int[] speed = {1.1.5.3.1};

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

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

The essential reason why binary search cannot be used in this problem is:

First of all, binary search is all about finding a threshold, m, by constantly approaching it. There are two important conditions: 1) if a certain value k does not work, then k + 1, k + 2… Definitely not. 2)

If I take a value of k rows, then K minus 1,k minus 2,k minus 3… Can do it. // It can also be the other way around. If k is not ok, then definitely not ok. If k is ok, then definitely ok.

You can only use dichotomy for these two features.

That’s where the problem comes in: my algorithm’s check method (whether it survives minute = mid) isn’t quite right. So if we don’t have condition 1 when minute = mid, mid + 1, mid + 2, we don’t have condition 2. If minute = mid row doesn’t prove mid-1, so does mid-2. Counterexamples are dist = {5,4,3,3,3} and speed = {1,1,5,3,1}.

Greedy solution:

Greedy strategy is also very simple, is to see the time, which monster arrived in a short time to destroy first. Since you can only kill one monster per minute, you will fail if your arrival time is greater than or equal to that round

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 {
            returni; }}return dist.length;
}
Copy the code