洛谷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;
}