10分求助,,,
查看原帖
10分求助,,,
340222
代码练习生楼主2020/7/20 16:25
#include<stdio.h>
#include<stdlib.h>

int
check(int *obs,int K,int N,int mid){
    int i,last=0;
    
    for(i=1;i<N;){
        if(obs[i]-last<=mid){           //二分是真的难写,,,
            last=obs[i++];
        }else{
            if(K<1)
                return 0;
            }
            last+=mid;
            K--;
    }
    return 1;
}

int
main(){
    int L,N,K,min,l,r=0,mid,*obstacles;
    
    scanf("%d%d%d",&L,&N,&K);
    obstacles=malloc(sizeof(int)*(N));
    for(l=0;l<N;l++){
        scanf("%d",obstacles+l);
    }
    l=0,r=L,min=L;
    while(l<=r){
        mid=(l+r+1)>>1;       //向上取整
        if(check(obstacles,K,N,mid)){
            r=mid-1;
            min=mid;
        }else{
            l=mid+1;
        }
    }
    printf("%d",min);
    return 0;
}

2020/7/20 16:25
加载中...