[2015年NOIP提高组] 跳石头
思路：本题是最大化最小值问题，考虑二分答案解决。
先写函数确定距离，然后看要搬的石头数满足题意吗。距离确定了，把间距小于确定距离的需要全部搬走。
然后向左或向右再找更小或大的距离，输出就可以了。
代码如下：
#include<iostream>
using namespace std;
int num[2000000];//岩石与起点的距离
int L,N,M;
int judge(int x)//判断预期最短距离M是否符合条件
{
int s=0,cnt=0;//当前距离起点的位置和记录搬走了多少石头
for(int i=1;i<=N+1;i++)//枚举第1到终点的n+1块石头
{
if(num[i]-s<x)//距离比预期短
cnt++;//搬走前面的石头
else
s=num[i];
}
if(cnt>M)//不满足最大的搬运量
return 0;
return 1;
}
int main()
{
int ans;
cin>>L>>N>>M;
num[0]=0;
for(int i=1;i<=N;i++)
cin>>num[i];
num[N+1]=L;
int l=0,r=L,mid;
while(l<=r)
{
mid=(l+r)/2;
if(judge(mid))//mid满足题意，向右找有没有距离更大的
{
l=mid+1;
ans=mid;
}
else//mid不满足题意，向小了的找
r=mid-1;
}
cout<<ans;
return 0;
}
标签：题意,NOIP,int,mid,距离,石头,num,2015 From： https://www.cnblogs.com/xdzxyingrui/p/16612711.html