0%

题解 P4998 信号站

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

kn106,0ai106

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

思路

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

设位置 i 的人家数有 bi 个,单次处理某个点的答案复杂度是 O(n) 的,即 fi=bj×|ij|

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

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

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

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

细节

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

为什么?我们如果只计算了 i[0,106] 的值,会忽略掉信号站建在负数位置的答案。

看个例子就懂了:

n = 3,位置 ai 都为 0,k = 3。

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

把所有位置向右平移 106 单位距离,计算答案的范围扩大一倍就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}
Powered By Valine
v1.5.2
  1. 1 だから僕は音楽を辞めた ヨルシカ
  2. 2 ノーチラス ヨルシカ
  3. 3 ただ君に晴れ ヨルシカ
  4. 4 願い~あの頃のキミへ~ 當山みれい
  5. 5 花に亡霊 ヨルシカ
  6. 6 DAYBREAK FRONTLINE 鹿乃
願い~あの頃のキミへ~ - 當山みれい
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.