POJ 3258 : River Hopscotch

概要

スタートの石とゴールの石が川の中にあって，その間の距離がLだけ離れている．スタートとゴールの間には，N個の石が一列に並んでいて，i番目の石はスタートからd_iだけ離れた位置にある．
スタートとゴールの石をM個以下だけ取り除いて，石（スタートとゴールも含む）の間の距離の最小値を最大化したい．

解法

許容する距離Dを仮定して二分探索．

距離Dだけ離せるかの判定は，スタートからDより小さい距離にある石を削除．その結果，残る石の中でスタートからの距離が最小のものを選び，それについて同様の処理を施す．これを続けていって最終的に削除した石の個数がM以下か確認すればいい．

int L, N, M;
int d[50010];

bool C(int a){
    int s = 0, cnt = 0;
    for(int i = 0; i < N; ++i){
        if(d[i] - s < a)
            ++cnt;
        else
            s = d[i];
    }
    if(L - s < a) ++cnt;
    return cnt <= M;
}

int main(){
    scanf("%d%d%d", &L, &N, &M);
    for(int i = 0; i < N; ++i){
        scanf("%d", &d[i]);
    }
    sort(d, d + N);

    int b = min(L - d[N-1], d[0]);
    for(int i = 1; i < N; ++i){
        b = min(b, d[i] - d[i-1]);
    }

    int res = -1;
    int lb = 1, ub = L;
    while(lb <= ub){
        int mid = (lb + ub) / 2;
        if(C(mid)){
            res = mid;
            lb = mid + 1;
        }
        else{
            ub = mid - 1;
        }
    }
    printf("%d\n", res);
    return 0;
}