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

题目链接

https://www.luogu.org/problemnew/show/P2678

题解

题目要求“最大值最小”,显然可以用二分答案的方法来解决本题,每次二分答案后,计算移走的石头数,如果移走的石头小于\(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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注