题干中说”最短距离尽可能长”,那么我们想到二分答案,
那么这道题的答案有没有一个可行的范围呢,该区间是否符合单调性呢?
来看范围:
显然对于初始的数据,从0到n+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)