洛谷P2678跳石头-程序员宅基地

noip2015提高组day2t1

题目里看到了最大值最小，可以判断用二分答案；

类似关键词还有最小值最大；

前边的最大最小是一种条件，在符合条件的情况下最大或最小；

在该题中则为拿走石头数与题里的m作比较，再一步步缩小mid范围

注意的是终点也有石头，还有坑点是函数里第一块石头也需要和起点作比较

 

#include<iostream>
#include<cstdio>
using namespace std;
int l,m,n,mid,x;
int  d[50005];
int fuck(int a){
    int ans=0;
    int rr=0;
    for(int i=1;i<=n;i++){
        if(d[i]-d[rr]<=mid){
            ans++;
        }else{
            rr=i;
        }
    }return ans;
}
int main(){
    scanf("%d%d%d",&l,&n,&m);
    d[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
    }
    n++;
    d[n]=l;
    int left,right;
    right=l;
    left=0;
    while(left<=right){
        mid=(left+right)/2;
        x=fuck(mid);
        if(x>m){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }printf("%d",left);
    return 0;
}