题干中说”最短距离尽可能长”,那么我们想到二分答案,

那么这道题的答案有没有一个可行的范围呢,该区间是否符合单调性呢?

来看范围:

显然对于初始的数据,从0n+1的相邻石头的距离,我们可以找到一个初始的dismin,这个可以作为left,

显然right=length(移除所有石头)。

来看单调性:

移除的石头数跟dismin肯定是递增关系的(移除石头是由于某两相邻石头间距太小)。

那么思路就是这样的:

以初始的dismin和length为答案区间的左右界,在其中二分查找一个最大的符合要求的石头最小间距

while(lef<r)
    {
        int mid=(lef+r+1)>>1;
        if(check(mid))
           lef=mid;
        else r=mid-1;
    }

这就是二分的代码,不用left和right是因为它俩都是关键字(我也不知道是哪个库的)

每次在lef和r中间取一个数,如果符合条件,那就把lef右移,看是否有更大的解,

如果不符合条件,就把r左移,再寻找。

在以上的查找过程中,lef始终是可行的,当while循环终止时,lef就是最优解了。

需要注意的地方:为什么min=(lef+r+1)/2呢,为什么不是(lef+r)/2呢?

请读者自己思考(提示:使用后者的话会TLE)

01-08 02:14