题解 P4998 信号站

一条路上有 n 户人家，坐标为 \(a_i\)，需要建 k 个不同位置的信号站，每个信号站的不合理值为所有人家到信号站的距离和，求不合理值最小的 k 个信号站不合理值之和。

\(k\le n\le 10^6,0\le a_i\le 10^6\)

我才不会告诉你我是趁着估值频繁更新的时候来水题解的。

思路

k,n 和坐标值域是同阶的。

设位置 i 的人家数有 \(b_i\) 个，单次处理某个点的答案复杂度是 \(O(n)\) 的，即 \(f_i=\sum b_j\times |i-j|\)。

这时候需要我们观察两个点的答案之间的关系，尝试利用状态重叠的部分减少复杂度。

常用技巧，推一下将信号站由 i 挪到 i+1 答案变化了多少：

• i 左边的点（包括 i 处）离信号站距离都加了一
• i 右边的点离信号站距离都减了一

那么我们要维护每个点左右边各有几个点，通过前缀和或者递推，可将每次查询降到 \(O(1)\)。

细节

我赌你写一发交上去，倒数第二个点会 WA。

为什么？我们如果只计算了 \(i\in [0,10^6]\) 的值，会忽略掉信号站建在负数位置的答案。

看个例子就懂了：

n = 3，位置 \(a_i\) 都为 0，k = 3。

那么三个信号站的位置分别为：-1，0，1。

把所有位置向右平移 \(10^6\) 单位距离，计算答案的范围扩大一倍就行。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

namespace RenaMoe {

template <typename TT> inline void read(TT &x) {}

typedef long long LL;

const int N = 1e6 + 9;
const int L = 1e6;

int n, k;
LL l, r, ans;
LL a[N<<1], f[N<<1];

inline void main() {
    read(n), read(k);
    for (int i = 1, x; i <= n; ++i)
        read(x), a[x+L]++;
    for (int i = 0; i <= L+L; ++i)
        f[0] += a[i] * i;
    // l,r 分别是该位置左右两边的点数
    r = n;
    for (int i = 1; i <= L+L; ++i) {
        l += a[i-1];
        f[i] = f[i-1] + l - r;
        r -= a[i];
    }
    sort(f, f+L+L+1);
    for (int i = 0; i < k; ++i)
        ans += f[i];
    printf("%lld\n", ans);
    return 0;
}