算法笔记之二分法解决极小化极大

算法笔记之二分法解决极小化极大

问题引入：

Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
所有 position 中的整数 互不相同 。
2 <= m <= position.length

问题分析：

题目要求返回最大化的最小磁力，这是这类问题的一个典型的标志。

正向分析题目，很难去解决。利用动态规划，贪心还是DFS都很棘手。

但是，这个时候反过来从结果出发，能不能枚举所有可能的最小磁力获得最大的磁力呢？

枚举是可以实现的，以为最小磁力可能出现的区间就是1到数组间隔最大值。

同时，结果的集合又呈单调性。在某个临界点之前都符合题意，之后的所有可能都不符合。

对于这种单调性的问题，二分法就是很好的解决方案了。

结论:从结果出发，二分搜索结果。见到极小化极大，极大化极小的问题，就可以考虑二分法

解题思路：

1. 根据题目的数据范围，二分法搜索的区间是[0,pos[n]-pos[0]];
2. 二分法的关键就是如何判定某个点是符合的：设k为某个最小的磁力，那么看数组上以k为距离可以放置多少小球，个数>m成立。
3. 二分法另外一个复杂的点在于边界控制问题。

代码：

public int maxMinDist(int[] position,int m){
    Arrays.sort(position);
    int n = position.length;
    int l=0,r=position[n-1];
    while (l<r){
        int mid = (l+r+1)>>1;
        if(checkMid(mid,n,m,position)){
            l = mid;
        }else {
            r = mid-1;
        }
    }
    return l;
}
public boolean checkMid(int mid,int n,int m,int[] position){
    int cnt = 1,temp = 0;
    for(int i=1;i<n;i++){
        if(position[i]-position[temp]>=mid){
            cnt++;
            temp=i;
        }
    }
    return cnt>=m;
}