题解 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 答案变化了多少：

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

总复杂度 O(n)。

细节

我赌你写一发交上去，倒数第二个点会 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;
}