cf427 E. Police Patrol（三分答案）

题意：

线段上固定着一些罪犯，第 \(i\) 个囚犯的位置为 \(a_i\)。现选一个位置建一个警局，每次出警从警局开一辆容量为m的警车，抓最多m个罪犯，然后开回警局。输出开车总路程的最小值。

\(1\le n, m\le 1e6, -1e9\le a_i\le 1e9\)

思路：

正解是线性的：先选一个点建警局，然后每次右移一点递推。但我不会。以下是歪解：

如果选定位置 x 建警局，那么我们可以线性地求出答案：从最左的罪犯的位置开始往右，但不越过x，每隔m取一个；然后从最右的罪犯的位置开始往左，但不越过x，每隔m取一个。

然后断定答案关于 x 是单峰凹函数，三分一下。不知道咋证明

const int N = 1e6 + 5;
ll n, m, a[N];

ll cal(ll x)
{
    ll res = 0, p = lower_bound(a + 1, a + 1 + n, x) - a;
    for(int i = 1; i < p; i += m) res += x - a[i];
    for(int i = n; i >= p; i -= m) res += a[i] - x;
    return 2 * res;
}

main()
{
    iofast;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    ll l = -INF, r = INF, lans, rans;
    while(l < r)
    {
        ll lmid = l + (r - l) / 3;
        ll rmid = r - (r - l) / 3;
        lans = cal(lmid), rans = cal(rmid);
        if(lans <= rans) r = rmid - 1;
        else l = lmid + 1;
    }
    cout << min(lans, rans);
}