形式化题目

一条直线上有 $N$ 个互不相同的正整数坐标 $x_1, x_2, \dots, x_N$。选出其中恰好 $P$ 个位置建邮局（邮局只能建在村庄上，集合记为 $S$，$|S| = P$），使

最小，输出这个最小值。坐标互不相同，$1 \leqslant N \leqslant 300$，$1 \leqslant P \leqslant 30$。

注意"建在其中的 $P$ 个村庄上"限定了邮局位置只能取自给定坐标集合，因此这是一个选择问题，不是连续选址。

正解

思路

第一步：排序，并说明可以只考虑"连续的一段"。

邮局只关心坐标之间的相对顺序，先把村庄按坐标升序排成 $x_1 < x_2 < \dots < x_N$。

设某两个相邻村庄 $x_a < x_b$ 分别由邮局 $u$、$v$ 服务。把分界线左右挪一格，两侧的距离和一增一减，一维情形下不会让答案变大。反复交换后总能得到一个最优解，使每个邮局负责的村庄恰好是一段连续下标区间。于是问题变成：

把前缀 $[1, N]$ 切成 $P$ 段（每段非空、段内连续），使各段的"单邮局代价"之和最小。

第二步：写成 DP。

设 $dp[k][i]$ 表示把前 $i$ 个村庄交给 $k$ 个邮局的最小代价，则

这里 $w(l, r)$ 表示"把连续一段村庄 $l..r$（下标 0 起）全部交给一个邮局"的最小距离和。边界 $dp[0][0] = 0$，其余 $dp[0][i>0] = \infty$（0 个邮局服务不了任何村庄）。答案是 $dp[P][N]$。

第三步：$w(l, r)$ 用中位数 $O(1)$ 算。

这一段只有一个邮局，建在中位数村庄上最优。把邮局从位置 $c$ 挪到 $c+1$：左侧所有村庄的距离各 $+1$，右侧各 $-1$。只要右侧村庄个数不少于左侧，距离和就不会变大，平衡点正是中位数。设 $m = \lfloor (l+r)/2 \rfloor$，用前缀和 $pre[i] = x_1 + \dots + x_i$ 得

样例里 $P = 1$ 时全部 10 个村庄共用一个邮局，$w(0, 9) = 117$；而 $P = 5$ 时答案是 $9$，说明分段带来的收益非常大。

第四步：找出真正的瓶颈。

朴素做法对每个 $i$ 都把 $j$ 从头扫一遍，复杂度 $O(PN^2)$。$N = 300, P = 30$ 时约 $1.35 \times 10^6$ 次转移，虽然能过，但完全没用上转移的结构。观察 $w$ 的性质：

$w(l, r)$ 满足四边形不等式 $w(a,c) + w(b,d) \leqslant w(a,d) + w(b,c)\quad (a \leqslant b \leqslant c \leqslant d)$。

这条不等式正是"交叉优于包含"的代数表达——两段交叉分配比一大一小包含分配更省。它的标准推论是决策单调性：

即"前 $i$ 个村庄的最优分割点"随 $i$ 单调不减。下表用题面样例（$N = 10$）实际算出的 $dp$ 与 $opt$ 验证了这一点（可以拿 problem-analysis-workspace/viz_render.py 复现）：

每一行的 $opt$ 都从左到右不减（$k=2$ 行是 $1,3,3,3,3,7,8,8$；$k=3$ 行是 $2,3,3,5,5,7,8,8$）。这就是可以直接拿来分治的依据。

第五步：用分治把每层降到 $O(N \log N)$。

有了决策单调性，算一层 $k$ 时可以这样递归（记 fill(lo, hi, opt_lo, opt_hi) 表示"$ndp[lo..hi]$ 的最优分割点都落在 $[opt\_lo, opt\_hi]$"）：

1. 取中点 $mid = \lfloor (lo+hi)/2 \rfloor$；
2. 只在 $j \in [opt\_lo,\ \min(mid-1, opt\_hi)]$ 里扫一遍，求出 $ndp[mid]$ 与 $opt_k(mid)$；
3. 左半边 $[lo, mid-1]$ 的分割点一定 $\leqslant opt_k(mid)$，右半边一定 $\geqslant opt_k(mid)$，各自带新界递归。

第 2 步里的 min(mid-1, opt_hi) 上界不能省：它同时保证 $j < mid$（段非空）和 $j$ 落在已知范围内。每一层的总扫描量是 $O(N \log N)$，$P$ 层合计 $O(PN\log N)$。

下面这张图画出样例中 $k=2, i=4$ 这一格的计算过程，帮助建立"枚举分割点"的直观印象。

flowchart LR
    subgraph tree ["分治：算 ndp[2..10]，opt 界 [1, 9]"]
        mid["mid = 6<br/>扫 j∈[1,5] → ndp[6]=5, opt=3"]
        mid --> L["左 [2,5]，opt 界 [1, 3]"]
        mid --> R["右 [7,10]，opt 界 [3, 9]"]
        L --> L2["mid = 3<br/>扫 j∈[1,2] → ndp[3]=1, opt=1"]
        R --> R2["mid = 8<br/>扫 j∈[3,7] → ndp[8]=21, opt=7"]
    end

关键在于每个 $mid$ 只扫一个被上下界夹住的小窗口，而不是整段前缀：算 ndp[3] 时只需看 $j \in \{1,2\}$，算 ndp[8] 时虽然窗口较大，但它已经把右半边的 $opt$ 界收窄到 $[7, 9]$，后面两个位置的枚举量随之骤降。整层的扫描总量因此是 $O(N\log N)$ 而非 $O(N^2)$。

最后还要处理一个边界：若 $P \geqslant N$，每个村庄都能建一个邮局，答案是 $0$，直接短路返回（也让下面的逐层递推不必考虑"段数超过村庄数"）。

代码

segment_cost 是上面第三步的中位数公式（即 $w(l,r)$）；layer 负责一整层 $k$ 的转移；内层 fill 就是第五步的分治，靠 opt_lo / opt_hi 两个界把每层的扫描量压到 $O(N\log N)$；solve 只做读入、排序、前缀和、逐层推进和输出。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 邮局：DP + 分治优化（代价满足四边形不等式，最优分割点单调）
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll INF = 1000000000000000000LL;

int n, p;
vector<ll> xs;  // 排好序的村庄坐标
vector<ll> pre; // pre[i] = 前 i 个村庄的坐标和
vector<ll> dp, ndp;

// 把村庄 l..r（下标闭区间）全交给一个邮局时的最小距离和，建在中位数上最优
ll segment_cost(int l, int r) {
    if (l > r) {
        return 0;
    }
    int mid = (l + r) / 2;
    ll c = xs[mid];
    ll left = c * (mid - l + 1) - (pre[mid + 1] - pre[l]);
    ll right = (pre[r + 1] - pre[mid + 1]) - c * (r - mid);
    return left + right;
}

// 算 ndp[lo..hi]，已知这些位置的最优分割点都落在 [opt_lo, opt_hi]
void fill_range(int lo, int hi, int opt_lo, int opt_hi) {
    if (lo > hi) {
        return;
    }
    int mid = (lo + hi) / 2;
    ll best = INF;
    int best_j = opt_lo;
    int lim = min(mid - 1, opt_hi);
    for (int j = opt_lo; j <= lim; j++) {
        ll v = dp[j] + segment_cost(j, mid - 1);
        if (v < best) {
            best = v;
            best_j = j;
        }
    }
    ndp[mid] = best;
    fill_range(lo, mid - 1, opt_lo, best_j); // 左半边的最优分割点不超过 mid 的
    fill_range(mid + 1, hi, best_j, opt_hi); // 右半边的最优分割点不小于 mid 的
}

int main() {
    if (scanf("%d %d", &n, &p) != 2) {
        return 0;
    }
    xs.assign(n, 0);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &xs[i]);
    }
    sort(xs.begin(), xs.end()); // 邮局只关心相对顺序
    pre.assign(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + xs[i];
    }

    if (p >= n) { // 邮局够多，每个村庄都建一个
        printf("0\n");
        return 0;
    }

    dp.assign(n + 1, INF);
    dp[0] = 0; // 0 个邮局：只有“前 0 个村庄”代价为 0
    for (int k = 1; k <= p; k++) {
        ndp.assign(n + 1, INF);
        fill_range(k, n, k - 1, n - 1);
        dp = ndp;
    }
    printf("%lld\n", dp[n]);
    return 0;
}

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 23:33
# update_at: 2026-10-01 23:33

import sys
from itertools import accumulate

INF = 10 ** 18  # “不可达”哨兵；真实答案不超过 N × 10000 = 3 × 10⁶，远小于它


def segment_cost(xs: list[int], pre: list[int], l: int, r: int) -> int:
    """把村庄 l..r（闭区间，按下标）全交给一个邮局时的最小距离和。

    坐标已升序，建在中位数的那个村庄上最优；左右两侧各自用前缀和一次算完。
    l > r 是空区间，返回 0。
    """
    mid = (l + r) // 2
    c = xs[mid]                                  # 中位数村庄的坐标
    left = c * (mid - l + 1) - (pre[mid + 1] - pre[l])
    right = (pre[r + 1] - pre[mid + 1]) - c * (r - mid)
    return left + right


def layer(dp: list[int], xs: list[int], pre: list[int], k: int) -> list[int]:
    """由“k-1 个邮局”的代价表 dp 推出“k 个邮局”的代价表 ndp[0..n]。

    ndp[i] = min_{j<i} dp[j] + cost(j, i-1)：前 j 个村庄交给 k-1 个邮局，
    第 k 个邮局负责剩下的 j..i-1 这一段。代价函数满足四边形不等式，
    所以最优分割点 j 随 i 单调不减，于是用分治把每层的 O(n²) 降成 O(n log n)。
    """
    n = len(xs)
    ndp = [INF] * (n + 1)

    def fill(lo: int, hi: int, opt_lo: int, opt_hi: int) -> None:
        """算 ndp[lo..hi]，已知这些位置的最优分割点都落在 [opt_lo, opt_hi]。"""
        if lo > hi:
            return
        mid = (lo + hi) // 2
        best, best_j = INF, opt_lo
        for j in range(opt_lo, min(mid - 1, opt_hi) + 1):
            value = dp[j] + segment_cost(xs, pre, j, mid - 1)
            if value < best:
                best, best_j = value, j
        ndp[mid] = best
        fill(lo, mid - 1, opt_lo, best_j)     # 左半边的最优分割点不超过 mid 的
        fill(mid + 1, hi, best_j, opt_hi)     # 右半边的最优分割点不小于 mid 的

    fill(k, n, k - 1, n - 1)
    return ndp


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, p = next(data), next(data)

    xs = sorted(next(data) for _ in range(n))  # 邮局只关心相对顺序，先排序
    pre = [0, *accumulate(xs)]                 # pre[i] = 前 i 个村庄的坐标和

    if p >= n:                                 # 邮局够多，每个村庄都建一个
        print(0)
        return

    dp = [INF] * (n + 1)                       # 0 个邮局：只有“前 0 个村庄”代价为 0
    dp[0] = 0
    for k in range(1, p + 1):
        dp = layer(dp, xs, pre, k)

    print(dp[n])


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：排序 $O(N\log N)$；内层分治每层 $O(N\log N)$，共 $P$ 层，合计 $O(PN\log N)$。朴素做法为 $O(PN^2)$；$N = 300, P = 30$ 时两者实测都在 $0.02$ s 量级，但分治版与题目标签"四边形不等式"给出的标准写法同阶。
• 空间复杂度：dp、ndp、pre 各 $O(N)$，递归栈 $O(\log N)$，合计 $O(N)$；实测峰值约 $15$ MB，远低于 $128$ MB 限制。

数据说明

数据仓 10 个 .out 是生成事故文件：第 1 行形如 N P 答案，第 2 行把输入坐标原样回显。例如 POST3.out 开头是

1
210 5 9
1 2 3 6 7 9 11 22 44 50

而题面的输出格式只要求"输出一个整数"，ROJ 官网该题的样例输出也正是单独的一个 9；两个官方数据镜像（csps.de5.net、oidata.cc.cd）的 3178.tar.zst 里都是同样内容，说明这是上游数据缺陷而非本地损坏。逐字节比对对任何符合题面的解都必然失败。

本次按仓库既有先例（同 roj/3006）处理：把每个 .out 收敛为第 1 行的第 3 个字段（真实答案），并同步 data.json 的文件大小。修复前先用一份独立编写的 $O(PN^2)$ 朴素 DP 交叉验证——10 组数据里朴素 DP、分治版 main.py、.out 内嵌答案三者完全一致（如 POST7 的 $300$ 个村庄、$P=1$ 均为 $1428420$）。修复后 verify.sh 3178 为 10/10 PASS，单测例约 $0.02$ s、峰值约 $15$ MB。

此外按任务要求未提供 brute.cpp，改为随机小数据自检：$n \leqslant 26$ 的 4600 组随机样例（含等距、聚集、大量并列最优）中，分治版与朴素 DP 答案全部一致，$opt$ 单调性 0 次违例。

图示解析

样例 $N = 10, P = 5$（坐标为 $1,2,3,6,7,9,11,22,44,50$）的最优分段如下图所示。

flowchart TD
    xs["升序坐标 1 2 3 6 7 9 11 22 44 50"] --> s1["段 A: 1,2,3 → 邮局在 2，代价 2"]
    xs --> s2["段 B: 6,7,9,11 → 邮局在 7，代价 7"]
    xs --> s3["段 C: 22 → 邮局在 22，代价 0"]
    xs --> s4["段 D: 44 → 邮局在 44，代价 0"]
    xs --> s5["段 E: 50 → 邮局在 50，代价 0"]
    s1 --> total["总代价 2+7+0+0+0 = 9"]
    s2 --> total
    s3 --> total
    s4 --> total
    s5 --> total

读图要点：每一段内部的邮局都建在该段的中位数村庄上。段 A 的 $1,2,3$ 建在 $2$，两边各差 $1$，代价 $2$；段 B 的 $6,7,9,11$ 建在 $7$，距离和为 $1+0+2+4 = 7$；段 C、D、E 各自只含一个村庄，代价都是 $0$。总代价 $2+7+0+0+0 = 9$，与样例输出一致。这说明 $P$ 较大时，最优策略是把彼此靠近的村庄合到同一段（如 $6,7$ 与 $9,11$），而把稀疏的远端村庄各自单独成段——远端的 $22,44,50$ 间距过大，再给它们配一个邮局的边际收益已经不如把邮局让给左边密集区。

总结

• 题目是选择问题：邮局只能建在给定村庄上，排序后每个邮局只需负责一段连续下标区间。
• 单段最优解建在中位数村庄，配合前缀和可以 $O(1)$ 求出任意区间的代价 $w(l,r)$。
• 朴素 DP 是 $O(PN^2)$；利用 $w$ 的四边形不等式得到决策单调性 $opt_k(i) \leqslant opt_k(i+1)$，再用分治收窄每格的分割点枚举范围，降到 $O(PN\log N)$。
• 实现上必须注意 $j$ 的扫描上界取 $\min(mid-1, opt\_hi)$：既保证段非空，又保证不越出已知范围。
• $P \geqslant N$ 时答案为 $0$，直接短路。