Code Festival 2015 予選A D: 壊れた電車

感想

バグらせまくってつらい。

問題

壊れた電車

解法

二分探索 + Greedy

左寄せまたは右寄せをして全部の車両をカバーできるか判定する。

static void solve() {
    int n = in.nextInt();
    int m = in.nextInt();
    int[] x = new int[m];
    int[] y = new int[m];

    for (int i=0; i<m; i++) {
        x[i] = in.nextInt();
        y[i] = n + 1 - x[i];
    }
    Arrays.sort(y);

    long lb = -1, ub = Long.MAX_VALUE;
    for (int i=0; i<100; i++) {
        long mid = (lb + ub)/2;
        if (f(mid,n,x) || f(mid,n,y)) ub = mid;
        else lb = mid;
    }

    out.println(ub);
}

static boolean f(long t, int n, int[] x) {
    long l = 0;
    for (int i=0; i<x.length; i++) {
        if (x[i] - l - 1 > t) return false;

        long d = x[i] - l - 1;

        if (l >= x[i]) l = x[i] + t;
        else l = Math.max(x[i] + t - d*2, x[i] + (t - d)/2);
    }
    return l >= n;
}