http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1523

yy题。。开始居然把排序漏了。。

/*44ms,168KB*/

const int mx = 500005;

int d[mx], n, m;

bool ok(int dis)
{
    int i, nowd = 0, nowpos = 0, nextpos;
    For(i, m)
    {
        nextpos = Lowpos(d, n + 2, nowd + dis);
        if (nextpos == n + 2) return true;
        if (nextpos - nowpos == 1)
        {
            if (d[nextpos] > nowd + dis) return false;
            else if (nextpos == n + 1) return true;
        }
        else
        {
            if (d[nextpos] > nowd + dis) --nextpos;
            else if (nextpos == n + 1) return true;
        }
        nowd = d[nextpos], nowpos = nextpos;
    }
    return false;
}

int solve(int l, int r) /// 传入的一定要是开区间
{
    int m;
    while (l + 1 < r)
    {
        m = (l + r) >> 1;
        ok(m) ? r = m : l = m;
    }
    return r;
}

int main()
{
    int len, i, ans;
    SIII(len, n, m);
    Forr(i, 1, n + 1) SI(d[i]);
    d[n + 1] = len;
    sort(d, d + n + 2);
    PI(solve(0, len + 1));
    return 0;
}

Comments

comments powered by Disqus