Leetcode-1552. Magnetic force between two balls

link

1552. The magnetic force between the two balls

subject

Under the code name C-137 On the earth ,Rick Found that if he put two balls in his newly invented basket , There will be a special form of magnetic force between them .Rick Yes  n  An empty basket , The first  i  The position of the basket is  position[i] ,Morty  Want to put  m  Put a ball in these baskets , Between any two balls   Minimum magnetic force   Maximum .

It is known that if two balls are located at  x  and  y , Then the magnetic force between them is  |x - y| .

Give you an array of integers  position  And an integer  m , Please return to maximize the minimum magnetic force .

Example

Example 1：
Input ：position = [1,2,3,4,7], m = 3
Output ：3
explain ： take 3 Put the balls in the 1,4 and 7 The three baskets , The magnetic force between the two balls is [3, 3, 6]. The minimum magnetic force is 3 . We can't make the minimum magnetic force greater than 3 .

Example 2：
Input ：position = [5,4,3,2,1,1000000000], m = 2
Output ：999999999
explain ： We use the 1 and 1000000000 The basket has the minimum magnetic force and the maximum .

explain

• n == position.length
• 2 <= n <= 10^5
• 1 <= position[i] <= 10^9
• all  position  The integer Different from each other  .
• 2 <= m <= position.length

Ideas

Reference resources Try to answer the official questions

If this question is derived from the front, it is specific m The position of the ball will be more complicated , However , We can reverse judgment .

As the topic requires to maximize the minimum magnetic force , So the value we are looking for is a critical value ,

Suppose the answer is ans, That is, the minimum magnetic force is ans, So we know that less than ans Your answer must also be legal （ Because the answer is ans when , The balls are as far apart as possible , Less than ans Words , The balls can get closer and closer ）, But more than ans All values of are illegal , So we can do a binary search on the answer , Find the answer directly and reversely .

So how to judge whether it is legal or illegal ？ It's also very simple. , With greedy thinking , When the answer is ans when , That is, the minimum distance between two balls is ans, In order to minimize the waste of space , Let the distance between each ball be ≥ans The minimum value of , If it can fit in the basket ≥m A ball is legal , Otherwise it's illegal .

We are [left,right] Interval search of , The mean for mid, Do the following ：

• If the current mid legal , Then order ans=mid, And reduce the interval to [mid+1,right];
• If the current mid illegal , Then the interval is reduced to [left,mid−1].
• The minimum distance between two balls is 1, The maximum spacing is the position of the last basket - The position of the smallest basket , These two values are the initial left and right.

C++ Code

class Solution {
public:
    bool check(int x, vector<int>& position, int m) {
        int pre = position[0], cnt = 1;
        for (int i = 1; i < position.size(); ++i) 
        {
            if (position[i] - pre >= x) 
            {
                pre = position[i];
                cnt += 1;
            }
        }
        return cnt >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1, right = position.back() - position[0], ans = -1;
        while (left <= right) 
        {
            int mid = (left + right) / 2;
            if (check(mid, position, m)) 
            {
                ans = mid;
                left = mid + 1;
            } 
            else right = mid - 1;
        }
        return ans;
    }
};