[POI 2010] ZAB-Frog

题意

石头坐标严格递增。青蛙每次跳到距离排名第 $k$ 的石头，距离相同则选离源头最近（编号最小）的石头。对每个起点求跳 $m$ 次后的终点。

先看一个直接按题意模拟的朴素解：

cpp

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/**
 * 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-08-06 22:43
 * update_at: 2026-08-06 22:43
 */

// brute.cpp：小数据暴力解，直接按题意模拟 m 次跳跃，每次暴力找出第 k 近的石头。
// 只适合 n、m 都很小的情况，用来理解题意并辅助对拍。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, k;
long long m;
long long p[MAXN]; // 石头位置，严格递增

// 从石头 start 出发，走 m 步后停在哪个石头。
int simulate(int start) {
    int cur = start;
    for (long long step = 1; step <= m; step++) {
        // 把所有石头按 (距离, 编号) 排序，找出第 k 小的距离。
        vector<pair<long long, int>> dist;
        for (int i = 1; i <= n; i++) {
            if (i == cur) continue;
            dist.push_back(make_pair(llabs(p[i] - p[cur]), i));
        }
        sort(dist.begin(), dist.end());
        // 注意：平局（多个石头距离相同且都满足条件）时，
        // 题目要求选离源头最近（编号最小）的石头，不能直接取排序后的第 k 个。
        long long d_star = dist[k - 1].first;
        cur = INT_MAX;
        for (int i = 0; i < (int)dist.size(); i++) {
            if (dist[i].first == d_star) cur = min(cur, dist[i].second);
        }
    }
    return cur;
}

int main() {
    scanf("%d%d%lld", &n, &k, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &p[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%d", simulate(i));
    }
    printf("\n");
    return 0;
}

这个暴力每次跳跃都把全部石头按（距离, 编号）排序，找第 $k$ 小的距离，再在平局组内取编号最小的石头。它只适合 $n$ 、 $m$ 都很小的情况，但能精确复现题面规则。

思路

一句话本质：把跳 $m$ 次拆成"求一步目标"和"走 $m$ 步"——前者靠"最近 $k+1$ 块连续成窗口"用双指针在线性时间解决，后者靠"映射快速幂"用对数级时间完成，内存只需三个 O(n) 数组。

能不能把每跳一次的代价降下来？

暴力每跳一次都要扫描全部石头重新找第 $k$ 近。但第 $k$ 近只由当前所在石头和全体坐标决定，与之前跳了几次无关——所以每块石头的一步目标 nxt[i] 完全可以只算一次，后面复用它跳 $m$ 步。

怎么高效找一个石头的第 $k$ 近？

距离的分布有一个简单规律：石头坐标严格递增，所以越靠近 $i$ ，距离一定越小。离 $i$ 最近的石头一定在 $i$ 左右两边紧挨的位置上。顺着这条规律想——

离 $i$ 最近的 $k+1$ 块石头（含 $i$ 自己）在有序数组中是不是连续的？

是的。假如存在一个空洞（一块石头落在"最近 $k+1$ "之外，但它的左右邻居都在之内），那么它到 $i$ 的距离会介于两个邻居之间，矛盾。所以最近 $k+1$ 块一定是坐标上的一个连续区间 $[l, r]$ 。

这个窗口里按距离从近到远数是： $i$ 自己（距离 $0$ ）排第 $1$ ，往外两端对称递增，排到第 $k+1$ 块就是窗口两端中离 $i$ 较远的那块——正好是第 $k$ 近。两端距离相等时，窗口左端的石头编号更小，离源头更近，符合题目"平局取最左"的规则。

$i$ 每次只移一格，窗口要重新找吗？

不需要，窗口只会整体右移——用反证法：

当 $i$ 右移到 $i+1$ ，假设窗口向左移动了，变成 $[l-1,\ r-1]$ （新增最左点 $l-1$ ，移除最右点 $r$ ）。那么 $l-1$ 进入了"最近 $k+1$ "，而 $r$ 被挤了出去。

但 $l-1$ 是 $i$ 的旧窗口中 不存在 的石头。旧窗口 $[l, r]$ 是离 $i$ 最近的 $k+1$ 个，所以窗口外任何石头到 $i$ 的距离都不小于窗口内任意石头到 $i$ 的距离。特别的，石头 $l-1$ （窗外的）到 $i$ 的距离不小于石头 $r$ （窗内的）到 $i$ 的距离。而且如果两者等距，平局取左的规则会让编号更小的 $l-1$ 比 $r$ 更优先进入窗口——既然 $l-1$ 不在而 $r$ 在，必然有严格大于。

（用位置差表示距离）所有石头都在一维直线上，距离就是坐标差的绝对值。又因为 $l-1 < i < r$ ，两段距离可以丢掉绝对值直接写成：

\underbrace{p_i - p_{l-1}}_{\text{dist}(l-1,\,i)} \;>\; \underbrace{p_r - p_i}_{\text{dist}(i,\,r)} \qquad\Longrightarrow\qquad p_{l-1} + p_r < 2 p_i \tag{1}

现在把 $i$ 换成 $i+1$ 。关键的一步：因为 $l-1 < i < i+1$ 共线，三点共线时距离满足加性分解（退化的三角不等式，恰好取等）：

下面解释这个数学知识。

三角不等式是说：平面上任意三个点 A、B、C 之间，"走直线"不会比"经 B 绕路"更长——即

\text{dist}(A, C) \le \text{dist}(A, B) + \text{dist}(B, C)

两边之和大于等于第三边。当三个点在一条直线上且 B 恰好落在 A 和 C 的中间时，不等号变成等号：

\text{dist}(A, C) = \text{dist}(A, B) + \text{dist}(B, C)

因为从 A 到 C 没有更短的路径，A→B→C 恰好依次走过整条线段。

本题所有石头都在一条小溪（直线）上，所以这个取等情形天然成立。具体到这里： $l-1$ 、 $i$ 、 $i+1$ 三个位置从左到右排列在直线上：

text

1
2
3p_{l-1}  -------  p_i  ---  p_{i+1}
|<--- dist(l-1, i) --->|<-d->|
|<------ dist(l-1, i+1) ------>|

$i$ 夹在 $l-1$ 和 $i+1$ 之间，所以"从 $l-1$ 到 $i+1$ "的距离，恰好等于"从 $l-1$ 到 $i$ "再加上"从 $i$ 跳到 $i+1$ "这两段之和：

\text{dist}(l-1,\,i+1) = \underbrace{\text{dist}(l-1,\,i)}_{p_i - p_{l-1}} \;+\; \underbrace{\text{dist}(i,\,i+1)}_{p_{i+1} - p_i} = (p_i - p_{l-1}) + (p_{i+1} - p_i) = p_{i+1} - p_{l-1}

这一步拆分了 $\text{dist}(l-1,\,i+1)$ ，目的是把原来"关于 $i$ "的不等式 $(1)$ 转换为"关于 $i+1$ "的不等式——因为 $(1)$ 式告诉我们 $p_{l-1} + p_r$ 的上界是 $2p_i$ ，而加性分解把 $p_{i+1}$ 引了进来，于是可以用 $p_{i+1} > p_i$ 把上界从 $2p_i$ 提升到 $2p_{i+1}$ ，进而得出在 $i+1$ 处 $l-1$ 比 $r$ 更远的结论。

将 $(1)$ 式两端同时加上 $2(p_{i+1} - p_i)$ ——因为 $p_{i+1} > p_i$ ，不等式右侧严格增大：

\begin{aligned} 2p_{i+1} &> 2p_i > p_{l-1} + p_r \\[4pt] \Longrightarrow\quad \underbrace{p_{i+1} - p_{l-1}}_{\text{dist}(l-1,\,i+1)} &> \underbrace{p_r - p_{i+1}}_{\text{dist}(i+1,\,r)} \end{aligned}

也就是说， $r$ 离 $i+1$ 比 $l-1$ 更近。既然 $r$ 更近，如果 $l-1$ 在 $i+1$ 的"最近 $k+1$ "窗口中，那么 $r$ 必然也在——不可能出现 $l-1$ 进、 $r$ 出的情况。矛盾。

因此窗口的左、右边界都不可能左移，只能整体右移。用两个指针 $l, r$ 维护：当 $r+1$ 这块石头比 $l$ 离 $i$ 更近时，整体右移一格。 $l, r$ 只增不减，总移动 $O(n)$ ，每个 $i$ 均摊 $O(1)$ 。

单步目标算完了，跳 $m$ 次怎么办？

每块石头恰好有一条出边，把跳一步看作函数 $f$ 。跳 $m$ 次 = 求 $f^m$ ——和整数快速幂完全同构：把 $m$ 拆成二进制位，预处理 $f^2, f^4, f^8 \ldots$ ，每层做一次函数合成（平方）： $f^{2^{j+1}}(i) = f^{2^j}\bigl(f^{2^j}(i)\bigr)$ 。

关键在内存：直接存 60 层跳表要 $60 \times n \approx 240$ MB，远超 $128$ MB 限制。但平方运算只依赖当前层，用滚动写法——当前层 $F$ 、临时 $TMP$ 、答案 $ANS$ 三个 $O(n)$ 数组轮换——就把内存压到了约 24MB。

具体做法： $F$ 初始为 $f^1$ （单步目标）， $ANS$ 初始为原地。从低位到高位扫描 $m$ 的二进制位——该位为 $1$ 时把当前 $F$ 作用到 $ANS$ 上（ $ANS[i] \gets F[ANS[i]]$ ），然后平方 $F$ （ $TMP[i] \gets F[F[i]]$ ，交换 $F$ 和 $TMP$ ）。逻辑上先走低位块、再走高位块，恰好拼出 $m$ 步。

代码

cpp

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101/**
 * 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-08-06 22:43
 * update_at: 2026-08-06 22:58
 */

// P3509 [POI 2010] ZAB-Frog
// 每个石头一步跳到距它第 k 近的石头（平局取离源头最近），
// 求每个起点跳 m 次后的位置。
//
// 思路：
// 1) 双指针 O(n) 求出每个石头的单步目标 nxt[i]；
// 2) 把"跳一步"看成函数 f，用二进制倍增（映射的快速幂）求 f^m。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n, k;
long long m;           // 跳跃次数，最大 1e18
long long p[MAXN];     // 石头位置，严格递增

int nxt[MAXN];         // nxt[i]：从石头 i 跳一步到达的石头编号
int F[MAXN];           // 倍增滚动数组，F[i] 表示当前层 2^j 步能到达的石头
int TMP[MAXN];         // 平方时使用的临时数组
int ANS[MAXN];         // ANS[i]：从 i 出发已走完低位块后的位置

// 用双指针求所有石头的一步目标。
// 关键观察：离石头 i 最近的 k+1 块石头（含 i 自己）在有序数组中构成连续窗口 [l, r]；
// 第 k 近的石头就是窗口中离 i 较远的那个端点（两端距离相等时取左端，即离源头最近）。
void calc_next() {
    int l = 1;
    int r = k + 1;      // 初始窗口 [1, k+1]，保证第 1 块石头右边有 k 块
    for (int i = 1; i <= n; i++) {
        // 右边下一个石头比左端点更近时，整个窗口右移一格。
        // l、r 只增不减，所以总移动次数为 O(n)。
        while (r + 1 <= n && p[r + 1] - p[i] < p[i] - p[l]) {
            l++;
            r++;
        }
        if (p[r] - p[i] > p[i] - p[l]) {
            nxt[i] = r;   // 右端点严格更远，第 k 近在右边
        } else {
            nxt[i] = l;   // 左端点更远或两端等距，取左端（离源头最近）
        }
    }
}

// 映射的快速幂：对每个起点求 f^m 后的位置，结果写入 ANS。
// 与 rbook 模板 quick-pow 同构：m 的每一位为 1 时把当前层 f^(2^j) 作用到答案上，
// 每层再把函数平方成 f^(2^(j+1))（F[F[i]] 相当于映射合成两次）。
// 调用前要求 F 初始化为 f^1，ANS 初始化为原地（0 步）。
void jump_power(long long m) {
    while (m > 0) {
        if (m & 1) {                              // 当前 2^j 这一位是 1，走这一块
            for (int i = 1; i <= n; i++) {
                ANS[i] = F[ANS[i]];
            }
        }
        for (int i = 1; i <= n; i++) {             // 平方：f^(2^(j+1)) = f^(2^j) 两次
            TMP[i] = F[F[i]];
        }
        for (int i = 1; i <= n; i++) {
            F[i] = TMP[i];
        }
        m >>= 1;
    }
}

void read_input() {
    scanf("%d%d%lld", &n, &k, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &p[i]);
    }
}

void solve() {
    calc_next();

    // 每个点只有一条出边，所以"跳 2^j 步"可以当函数整体平方。
    for (int i = 1; i <= n; i++) {
        F[i] = nxt[i];     // 第 0 层：1 步
        ANS[i] = i;        // 0 步：还在原地
    }
    jump_power(m);         // 从低位到高位拼出 m 步

    for (int i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%d", ANS[i]);
    }
    printf("\n");
}

int main() {
    read_input();
    solve();
    return 0;
}

复杂度

双指针求单步目标 $O(n)$ ；倍增 $O(n \log m)$ 。总时间复杂度 $O(n \log m)$ ，空间 $O(n)$ 。

总结

第 $k$ 近的等价说法：最近 $k+1$ 块中离 $i$ 最远的那块。
最近 $k+1$ 块在有序数组中连续成窗口，且窗口单调右移，是双指针的典型特征。
每个点一条出边 ⟹ 跳 $m$ 步 = 函数复合，二进制倍增压层数；内存紧张时用滚动数组代替二维跳表。

图示解析

这张图展示从题目到最终解法的完整路线：

text

1
2
3
4
5
6
7
8
9
10
11
12题面：n 块石头（位置递增），每次跳到第 k 近（平局取最左），跳 m 次
   │
   ├─ 暴力（brute.cpp）：每跳一次全量排序找第 k 近，逐次模拟 m 次
   │    瓶颈：O(n·m·nlogn)，n=1e6、m=1e18 不可行
   │
   ├─ 关键观察 A：第 k 近 = 最近 k+1 块石头中离 i 最远的一块
   ├─ 关键观察 B：最近 k+1 块在有序数组中连续成窗口
   ├─ 关键观察 C：窗口随 i 单调右移
   │    └─ 双指针 O(n) 求出所有单步目标 nxt[i]
   │
   └─ 关键观察 D：每点一条出边，跳 m 次 = f^m
        └─ 二进制倍增（滚动平方）O(n log m) 拼出 m 步

从上到下看，题目先被拆成"求单步目标"和"走 m 步"两个子问题；前者靠窗口连续性用双指针 $O(n)$ 解决，后者靠函数图结构用倍增 $O(n \log m)$ 解决。两条线的瓶颈（全量排序、逐次模拟）恰好被两个观察分别消除。

目录

题意

思路

代码

复杂度

总结

图示解析