门户网站集群建设方案/谷歌seo引擎优化

解题方法：二分，因为移走石头的数目和最短的跳跃距离是单调关系，所以考虑用二分，并且一个距离可能有多个石头数目对应，表现在坐标图中就是一条平行于x轴的线段。

还有关于代码中的二分的循环我想详细说明一下：

high定位实际上界+1，是利用了左开右闭，这样的好处是当low=high时，区间中的元素就没有了，这样更易理解。因为肯定有解，所以经过循环low一定会等于当前解+1，然后寻找下一对于本题来说更优的解，所以到最后Low-1就是最后即最优的解；

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 50010
int l,n,m;
bool judge(int mid,int* rock)
{
int sum=0;
int tot=0;
int j=0;
for(int i=1;i<=(n+1);)
{
int did=rock[i]-rock[i-1];
if(sum+did<mid)
{
sum+=did;
i++;
tot++;
}
else
{
i++;
sum=0;
}
}
if(tot<=m) return true;//小了
else return false;//大了
}
int main()
{
while(scanf("%d",&l)!=EOF)
{
int rock[maxn];
scanf("%d %d",&n,&m);
int i;
rock[0]=0;
rock[n+1]=l;
for(i=1;i<=n;i++)
{
scanf("%d",&rock[i]);
}
int low=0;//本题的下界本应是最小的距离，但最小的距离不好找，就把0当做下界，要相信二分的高效
int high=l+1;
sort(rock,rock+(n+2));
while(low<high)
{
int mid=low+(high-low)/2;
if(judge(mid,rock)) 
low=mid+1;
else
high=mid;
}
printf("%d\n",low-1);
}
return 0;
}