“This is the second day of my participation in the First Challenge 2022.

M boys go to the toilet together (trumpet), how to avoid embarrassment to the greatest extent.

— Leetcode

preface

Hello, I’m One, welcome to my algorithm channel.

Only do interesting algorithms, only write algorithms for interviews.

Question

1552 the magnetic force between the two balls

Difficulty: Medium

Rick has n empty baskets, and the ith basket is in position[I]. Morty wants to put m balls in these baskets to maximize the minimum magnetic force between any two balls.

Known two balls if located in x and y, then the magnetic force between them for | x-y |.

Given an integer array position and an integer m, return the maximum minimum magnetic force.

Example 1:

Input: position = [1,2,3,4,7], m = 3 output: 3 explanation: place three balls in three baskets located at 1,4, and 7. The magnetic force between the two balls is [3, 3, 6]. The minimum magnetic force is 3. We can't get the minimum magnetic force above 3.Copy the code

Solution

The translation of this question is very vivid.

The question is to minimize the maximum, so how do you put the ball? — Spread them out evenly, that is, spread them out.

It’s not hard to think about binary search

Binary template

Add two binary templates first.

Template 1:

boolean check(int x) {}

int search(int left, int right) {
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}
Copy the code

The template 2:

boolean check(int x) {}

int search(int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) > >1;
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}
Copy the code

To do dichotomous questions, follow these steps:

  1. Write the loop condition:while (left < right), pay attention to isleft < rightRather thanleft <= right;
  2. Circulatory body, brainless writemid = (left + right) >> 1;
  3. implementationcheck()Delta function, let’s think about what we want to useleft = midorright = mid;
  4. ifleft = mid, then write the else statement without thinkingright = mid - 1And add +1 in mid calculation, i.emid = (left + right + 1) >> 1;
  5. ifright = mid, then write the else statement without thinkingleft = midAnd there is no need to change the calculation of mid;
  6. At the end of the loop, left is equal to right.

Kinds of antithesis

First sort, and then enumerate the distance between two adjacent balls in bisection. It only needs to count how many balls can be placed under the current distance, denoted as CNT. If CNT >= m, it indicates that this distance meets the condition. Continue binary search, and finally find the maximum spacing that meets the conditions.

Code

/ * * *@authorA coding * /

Copy the code

The last

Thumbs up, thumbs up, and fucking thumbs up!