LeetCode 1552. 两球之间的磁力（极小极大化 二分查找）

输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，
两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。
我们没办法让最小磁力大于 3 。

示例 2：
输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。
 
提示：
n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
所有 position 中的整数 互不相同 。
2 <= m <= position.length

class Solution {
	set<int> pos;
public:
    int maxDistance(vector<int>& position, int m) {
    	int l = 1, r = 1e9+1, dis, ans;
    	for(auto i : position)
    		pos.insert(i);
    	while(l <= r)
    	{
    		dis = (l+r)/2;
    		if(canPutM(m, dis))
    		{
    			ans = dis;
    			l = dis+1;
    		}
    		else
    			r = dis-1;
    	}
    	return ans;
    }

    bool canPutM(int m, int dis)
    {
    	int count = 1, p = *pos.begin();
    	auto it = pos.lower_bound(p+dis);
    	while(it != pos.end() && count < m)//放下了几个满足dis间距的球
    	{
    		++count;
    		p = *it;//下一个满足dis要求的
    		it = pos.lower_bound(p+dis);//二分查找下一个
    	}
    	return count == m; //可以放下这么多球
    }
};