[洛谷 2678,2855][USACO06DEC][NOIP2015]跳石头

题目链接

https://www.luogu.org/problem/P2678

https://www.luogu.org/problem/P2855

题解

题目要求“最大值最小”，显然可以用二分答案的方法来解决本题，每次二分答案后，计算移走的石头数，如果移走的石头小于 \(m\) 个，则在左半边搜索，否则在右半边搜索。

但注意，终点是 \(n+1\)，所以二分的边界条件是 \(l+1<r\)。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int stone[400100];
int main()
{
 int i,j,mid;
 int l,left,r,n,m;
 scanf("%d%d%d",&l,&n,&m);
 for(int i=1;i<=n;i++)
  scanf("%d",&stone[i]);
 stone[0]=0;
 stone[n+1]=l;
 left=0;
 r=l+1;
 while(left+1<r)
 {
  mid=(left+r)/2;
  int ans=0;
  i=0;
  while(i<=n)
  {
   j=i+1;
   while(stone[j]-stone[i]<mid&&j<=n+1) 
    j++;
   ans+=j-i-1;
   i=j;
  }
  if(ans<=m)left=mid;
  else r=mid; 
 }
 printf("%d",left);
 return 0;
}