自动搬运

查看原文

来自洛谷，原作者为

	RenaMoe 你好世界

搬运于2025-08-24 22:06:01，当前版本为作者最后更新于2020-08-26 18:20:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一条路上有 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)$。

总复杂度 $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;
}