洛谷P6246 [IOI2000] 邮局加强版加强版题解

题目链接：P6246 [IOI2000] 邮局加强版加强版

题意：

高速公路旁边有 \(n\) 个村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。

现在要建立 \(m\) 个邮局，邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式：

第一行包含两个整数，分别表示村庄的数量 \(n\) 和邮局的数量 \(m\)。

第二行共 \(n\) 个整数，表示每个村庄的坐标，第 \(i\) 个整数表示第 \(i\) 个村庄的坐标 \(a_i\)。

输出格式：

输出一行一个整数表示答案。

数据范围：

保证最终答案不超过 \(10^9\)。

保证 \(1 \leq m \leq n \leq 5 \times 10^5\)，\(0 \leq a_i \leq 2\times 10^6\)，且 \(a_i\) 的值在对应范围内均匀随机

本来是看题解区都没写dp式子，想找一篇写了的看看，没想到学了个最快的解法

本解法的复杂度为 \(\mathcal{O}(n \log V)\) ，且无需数据随机，思路是 wqs二分 + 斜率优化。

首先有一个经典结论（~~我反正不知道~~）

设 \(w(l,r)\) 表示在 \(\left\lfloor\frac{l+r}{2}\right\rfloor\) 处建立邮局，\(l\) 到 \(r\) 的村庄全部去往该邮局的距离之和，则有递推式 \[ f_{i,j} = \min_{0 \le t < i} \{f_{t,j-1} + w(t + 1, i)\} \] 由于 \(w(l,r)\) 满足四边形不等式，故 \(\mathrm{Ans}_m=f_{n,m}\) 是关于 \(m\) 的凸函数（并且是下凸函数）。证明见 link

那么考虑 wqs 二分以消去 \(m\) 的限制，即二分的斜率为 \(K\)

因为这是一个下凸函数，注意到 \[ 0 \ge K_{\rm Ans} = \mathrm{Ans}_{m+1} - \mathrm{Ans}_{m} \ge \mathrm{Ans}_{n} - \mathrm{Ans}_m = -\mathrm{Ans}_m \] 所以我们二分范围取 \([-10^9,0]\) 即可

设 \(f_i\) 为考虑前 \(i\) 个村庄的最小花费，即 \(S_i = \sum_{j=1}^{i} a_j\) ，则有 \[ f_i=\min _{1 \leq j \leq i}\left\{\left(S_i-S_j\right)-(i-j) a_j+\min _{0 \leq k<j}\left\{(j-k) a_j-\left(S_j-S_k\right)+f_k\right\}\right\}-K \] 转移枚举在位置 \(j\) 放邮局即可。

记 \(g_j = \displaystyle \min _{0 \leq k<j}\left\{(j-k) a_j-\left(S_j-S_k\right)+f_k\right\}\) ，很明显是一个斜率优化。

再把 \(g_j\) 代入进去，即 \(f_i=\min _{1 \leq j \leq i}\left\{\left(S_i-S_j\right)-(i-j) a_j+g_j\right\}-K\) ，这又是一个斜率优化。

时间复杂度 \(\mathcal{O}(n \log V)\) ，\(V\) 是值域。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

int n, m, a[N], s[N], f[N], g[N], q1[N], q2[N], cntf[N], cntg[N];
int check(int K)
{
    static const auto x1 = [](int x) { return x; };
    static const auto y1 = [](int x) { return s[x] + f[x]; };
    static const auto x2 = [](int x) { return a[x]; };
    static const auto y2 = [](int x) { return -s[x] + x * a[x] + g[x]; };
    f[0] = 0, cntf[0] = 0; int *st1 = q1, *en1 = q1, *st2 = q2, *en2 = q2; *en1++ = 0;
    for(int i = 1; i <= n; i++)
    {
        while(en1 - st1 > 1)
        {
            if (
                make_pair(y1(*st1) - a[i] * x1(*st1), cntf[*st1])
                < make_pair(y1(st1[1]) - a[i] * x1(st1[1]), cntf[st1[1]])
            ) break; else ++st1;
        }
        cntg[i] = cntf[*st1]; g[i] = i * a[i] - s[i] + y1(*st1) - a[i] * x1(*st1);
        while(en2 - st2 > 1)
        {
            if (
                make_pair((y2(i) - y2(en2[-1])) * (x2(en2[-1]) - x2(en2[-2])), cntg[i])
                > make_pair((y2(en2[-1]) - y2(en2[-2])) * (x2(i) - x2(en2[-1])), cntg[en2[-1]])
            ) break; else --en2;
        }
        *en2++ = i;
        while(en2 - st2 > 1)
        {
            if (
                make_pair(y2(*st2) - i * x2(*st2), cntg[*st2])
                < make_pair(y2(st2[1]) - i * x2(st2[1]), cntg[st2[1]])
            ) break; else ++st2;
        }
        cntf[i] = cntg[*st2] + 1;
        f[i] = -K + s[i] + y2(*st2) - i * x2(*st2);
        while(en1 - st1 > 1)
        {
            if (
                make_pair((y1(i) - y1(en1[-1])) * (x1(en1[-1]) - x1(en1[-2])), cntf[i])
                > make_pair((y1(en1[-1]) - y1(en1[-2])) * (x1(i) - x1(en1[-1])), cntf[en1[-1]])
            ) break; else --en1;
        }
        *en1++ = i;
    }
    return cntf[n];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    int l = -1e9, r = 0;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid) <= m) l = mid; else r = mid - 1;
    }
    check(l); cout << f[n] + m * l << '\n';
    return 0;
}