CODE FESTIVAL QUAL A - D 壊れた電車

2015/09/27 (Sun) AtCoder CODE FESTIVAL 二分探索 貪欲

問題

問題文

方針

答えの時間 T を決めて，それが可能か判定する関数を作り，二分探索． 現時点で修理が完了した最も右の車両を変数 done で持ち， そこより右のどこまで終わらせられるかを求める．

二分探索は第一感でわかったけど判定部分が書けなかった…

実装

ll n;
ll m;
ll x[100010];

bool check(ll T){
    if(T == -1) return false;
    ll done = 0;
    rep(i,m){
        ll nx = done;
        {
            ll rem = T;
            rem -= x[i] - (done + 1);
            if(rem >= 0){
                ll can = (done + 1) + rem;
                nx = max(nx, can);
            }
        }
        {
            ll rem = T;
            rem -= x[i] - (done + 1);
            if(rem >= 0){
                ll can = x[i] + rem/2;
                nx = max(nx, can);
            }
        }
        done = min(i != m-1 ? x[i+1]-1 : n, nx);
    }
    return done == n;
}

ll solve(){
    if(m == 1) return n-1 + min(x[0]-1, n-x[0]);
    ll l = -1, r = n*2;
    // xxxxoooo
    //    lr
    while(l+1 < r){
        ll m = (l+r)/2;
        if(check(m)) r = m;
        else l = m;
    }
    return r;
}

signed main(){
    while(cin >> n){
        cin >> m;
        rep(i,m) cin >> x[i];
        cout << solve() << endl;
    }
}