把「能看到的最高的山」归约为两侧斜率最大的点,再用单调栈求出每个山顶转向的第一站,沿链递推步数,整体 O(n)。
OJ: roj
题目 ID: 1788
难度:提高+/省选-
标签:单调栈几何贪心python
创建: 2026-10-08 08:10
更新: 2026-10-08 08:10
形式化题目
平面上给出
可见性:山顶
山的高低:对两个山顶
把这个二元组压成排序键
爬山规则:全局维护一个"到目前为止看到过的最高山顶"
- 当前在
,若 就停下; - 否则
(按 取大); - 朝
的方向移动一格: 就走到 ,否则走到 。
输出:对每个起点
样例:
0
1
4
3比如从
正解
思路
朴素做法。 对每个点
关键观察(难点):能看到的最高山顶 = 斜率最大的山顶。
固定
设
一定能被看到。 若某个中间点 不在 下方, 就有 ;由 最大可知必须相等(共线), 但取最靠左的 排除了"更近的 也在此斜率上"的情况,矛盾。 - 比
更高的点都看不到。 设 且 。 若 能被看到,那么中间所有点都严格在 下方, 特别是 ,与 取最大矛盾。
所以
于是
求斜率最大的点:链式跳跃(摊还
设
实现上,代码用 ys / xs 的交叉相乘代替除法,并给"向左"的情况整体乘 main.py 的 far_side。
从
设爬山者在
- 在
之前, 不变,方向不变,所以步子是一路直着走的; - 到了
, 且 。
关键在最后一句:在
而没有这种
于是只要对每个
求
收尾:沿链递推。 这里还需要一条除成环的性质:只要
用样例走一遍。 山顶
| 向左斜率最大者 | 向右斜率最大者 | |||||
|---|---|---|---|---|---|---|
| 1 | — | — | 1 | 1 | 0 | |
| 2 | 1 | 4 | 1 | 1 | ||
| 3 | 2 | 4 | 4 | 4 | ||
| 4 | 1 | — | 1 | 1 |
逐格核对第 2、3 两行。
代码
Python 版:
#!/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-08 08:10
# update_at: 2026-10-08 08:10
import sys
type Coords = list[int] # 一维坐标数组(x 或 y),下标就是山顶编号
def far_side(xs: Coords, ys: Coords, sgn: int) -> Coords:
"""far[i]:从 i 沿 sgn 方向(+1 向右 / -1 向左)看,斜率最大的山顶编号。
这就是该方向能看到的最高山顶:斜率最大的点必然可见,而比它更高的点都被它挡住。
若 far[i] 再往远处还有一个更陡的点 far[far[i]],就顺着已算好的答案直接跳过去,
链式跳跃(far[i] 不断替换成 far[far[i]])让整体摊还到 O(n)。
边界处没有更远处的点,far[i] 就是 i 自己。
"""
n = len(xs)
far = [min(max(i + sgn, 0), n - 1) for i in range(n)]
for i in (range(n - 3, -1, -1) if sgn == 1 else range(2, n)):
j = far[i]
while True:
k = far[j] # j 再往远处看的下降点
# 乘 sgn 把"向左看"折成同一个不等式:斜率(i,j) 严格小于 斜率(i,k) 才继续跳
steeper = (ys[k] - ys[i]) * (xs[j] - xs[i]) * sgn \
> (ys[j] - ys[i]) * (xs[k] - xs[i]) * sgn
if not steeper:
break
j = far[j]
far[i] = j
return far
def walk_steps(xs: Coords, ys: Coords) -> Coords:
"""ans[i]:从山顶 i 出发爬到最高山顶所需的步数。"""
n = len(xs)
if n == 1:
return [0]
hi = max(range(n), key=lambda i: (ys[i], xs[i])) # 全局最高:y 大者,y 同取 x 大者
rj, lj = far_side(xs, ys, 1), far_side(xs, ys, -1)
# f[i]:i 真正能看到的最高山顶 = {i, 左侧斜率最大者, 右侧斜率最大者} 中 rank 最高的。
# 边界只有一侧有候选;两侧都不比 i 高时 f[i] 就退回 i(即在此停住)。
f = [hi] * n
for i in range(n):
if i == hi:
continue
f[i] = max(i, lj[i], rj[i], key=lambda p: (ys[p], xs[p]))
fkey = [ys[f[i]] * 1000001 + xs[f[i]] for i in range(n)] # 山顶优劣压成整数:先比 y 再比 x
del rj, lj # 两侧最远可见点用完就丢,给后面的栈/链表腾内存
# nxt[i] / prv[i]:右侧 / 左侧第一个 fkey 严格大于 fkey[i] 的山顶(单调栈 O(n))
# 值为 -1 表示这一侧根本没有更高的山顶
nxt, prv = [-1] * n, [-1] * n
st: list[int] = []
for i in range(n - 1, -1, -1):
while st and fkey[st[-1]] <= fkey[i]:
st.pop()
nxt[i] = st[-1] if st else -1
st.append(i)
st = []
for i in range(n):
while st and fkey[st[-1]] <= fkey[i]:
st.pop()
prv[i] = st[-1] if st else -1
st.append(i)
# par[i]:最优路径上 i 的下一站。朝 f[i] 走的途中只有"第一个能看得更高"的位置才会
# 改目标,先到那里;沿途没人看得更高,就一口气走到 f[i]。
par = [hi] * n
for i in range(n):
if i == hi:
continue
v = f[i]
if v > i:
k = nxt[i]
par[i] = k if k != -1 and k < v else v
else:
k = prv[i]
par[i] = k if k != -1 and k > v else v
del fkey, nxt, prv, f # 同上:定完 par 就不再需要这些中转数组
# 沿 par 链递推:ans[i] = |i - par[i]| + ans[par[i]]。
# 每条链的终点都是全局最高峰 hi,链上每个山顶的答案只会被填一次,总代价 O(n)。
ans = [-1] * n # -1 表示该山顶的步数还没算出来
ans[hi] = 0
for i in range(n):
if ans[i] >= 0:
continue
path: list[int] = []
cur = i
while ans[cur] < 0: # 先沿 par 走到一个已有答案的位置
path.append(cur)
cur = par[cur]
base = ans[cur]
for v in reversed(path): # 再倒着把路上每个山顶的步数补齐
base += abs(v - par[v])
ans[v] = base
return ans
def solve() -> None:
tokens = sys.stdin.buffer.read().split()
n = int(tokens[0])
# 这里用切片而不是逐个数 next():一共 10^6 个数,切片 + map(int) 全在 C 层跑,
# 比在 Python 层调 10^6 次 next() 快约一倍(实测 0.06s vs 0.10s)。
xs = list(map(int, tokens[1:2 * n + 1:2])) # 奇数位是 x,x 坐标严格递增
ys = list(map(int, tokens[2:2 * n + 1:2])) # 偶数位是 y
del tokens # 原始 token 列表有 10^6 个 bytes 对象,尽早释放
print('\n'.join(map(str, walk_steps(xs, ys))))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-08 08:10
* update_at: 2026-10-08 08:10
*/
// main.cpp:ROJ 1788《爬山》。
// 与 main.py 同一算法:先 O(n) 求出每个山顶真正能看到的最高山顶 f[i],
// 再用"单调栈求首个更高者"定出每个山顶在最优路径上的下一站 par[i],
// 最后沿 par 链把步数累加起来,全程 O(n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500005; // 山顶数上限 5e5
int N; // 山顶个数
int X[MAXN], Y[MAXN]; // 山顶坐标,X 严格递增
int Rj[MAXN], Lj[MAXN]; // 向右 / 向左能看到的最远山顶(即斜率最大者)
int f[MAXN]; // f[i]:山顶 i 看得到的最高山顶(等高取 x 大者)
int nxt[MAXN], prv[MAXN]; // 首个 f 值比 i 更大 的右侧 / 左侧山顶
int par[MAXN]; // 最优路径上 i 的下一站
int stk[MAXN], path[MAXN]; // 单调栈、沿 par 链回溯时的路径
ll ans[MAXN]; // 答案:从 i 出发走过的边数(-1 表示还没算出)
// 把"山顶的优劣"压成一个整数键:先比 y,y 相同再比 x,越大越高
inline ll key(int p) { return (ll)Y[f[p]] * 1000001 + X[f[p]]; }
// a 是否严格比 b 高:y 大者高,y 相同取 x 大者
inline bool rankBetter(int a, int b) {
return Y[a] > Y[b] || (Y[a] == Y[b] && X[a] > X[b]);
}
// slope(i,j) < slope(i,k),左右端点全部交叉相乘,不出现除法
inline bool slopeLt(int i, int j, int k) {
return (ll)(Y[j] - Y[i]) * (X[k] - X[i]) < (ll)(Y[k] - Y[i]) * (X[j] - X[i]);
}
// slope(p,i) < slope(q,i),公共右端点 i(向左看时用)
inline bool slopeLt2(int p, int q, int i) {
return (ll)(Y[i] - Y[p]) * (X[i] - X[q]) < (ll)(Y[i] - Y[q]) * (X[i] - X[p]);
}
int main() {
if (scanf("%d", &N) != 1) return 0;
for (int i = 0; i < N; i++) scanf("%d %d", &X[i], &Y[i]);
if (N == 1) { printf("0\n"); return 0; }
// 全局最高山顶:y 大者优先,y 相同取 x 大者
int hi = 0;
for (int i = 1; i < N; i++)
if (rankBetter(i, hi)) hi = i;
// ① Rj[i]:从 i 向右看的斜率最大者,也就是 i 向右能看到的最高山顶。
// 从右往左扫,Rj 用"斜率严格递增就继续往右跳"的链式加速。
for (int i = 0; i < N; i++) Rj[i] = i + 1;
Rj[N - 1] = N - 1;
for (int i = N - 3; i >= 0; i--)
while (Rj[i] != N - 1 && slopeLt(i, Rj[i], Rj[Rj[i]]))
Rj[i] = Rj[Rj[i]];
// ② Lj[i]:从 i 向左看的斜率最大者,同理(从左往右扫)
for (int i = 0; i < N; i++) Lj[i] = i - 1;
Lj[0] = 0;
for (int i = 2; i < N; i++)
while (Lj[i] != 0 && slopeLt2(Lj[Lj[i]], Lj[i], i))
Lj[i] = Lj[Lj[i]];
// ③ f[i]:i 能看到的最高的山 = {i, 左侧斜率最大者, 右侧斜率最大者} 中 rank 最高者
for (int i = 0; i < N; i++) {
if (i == hi) { f[i] = hi; continue; }
int cand = i; // 先拿自己当基准(两侧都被挡住时退回自己)
if (i > 0 && rankBetter(Lj[i], cand)) cand = Lj[i];
if (i < N - 1 && rankBetter(Rj[i], cand)) cand = Rj[i];
f[i] = cand;
}
// ④ nxt[i] / prv[i]:首个"f 值严格大于 f[i]"的山顶(单调栈 O(n))
for (int i = N - 1, top = 0; i >= 0; i--) {
while (top && key(stk[top - 1]) <= key(i)) top--;
nxt[i] = top ? stk[top - 1] : -1;
stk[top++] = i;
}
for (int i = 0, top = 0; i < N; i++) {
while (top && key(stk[top - 1]) <= key(i)) top--;
prv[i] = top ? stk[top - 1] : -1;
stk[top++] = i;
}
// ⑤ par[i]:走向 f[i] 的途中,第一个"能看到更高山顶"的位置才是真正的转向点;
// 如果沿途都没人能看得更高,就一口气走到 f[i]。
for (int i = 0; i < N; i++) {
if (i == hi) { par[i] = hi; continue; }
int v = f[i];
if (v > i) {
int k = nxt[i];
par[i] = (k != -1 && k < v) ? k : v;
} else {
int k = prv[i];
par[i] = (k != -1 && k > v) ? k : v;
}
}
// ⑥ 沿 par 链递推:ans[i] = |i - par[i]| + ans[par[i]]。
// 每条链的终点都是全局最高峰 hi,且链上答案只会被算一次,总代价 O(N)。
for (int i = 0; i < N; i++) ans[i] = -1;
ans[hi] = 0;
for (int i = 0; i < N; i++) {
if (ans[i] >= 0) continue;
int len = 0, cur = i;
while (ans[cur] < 0) { path[len++] = cur; cur = par[cur]; } // 先走到已知答案处
ll base = ans[cur];
while (len--) { // 再倒着把路径填回去
cur = path[len];
base += (cur > par[cur] ? cur - par[cur] : par[cur] - cur);
ans[cur] = base;
}
}
for (int i = 0; i < N; i++) printf("%lld\n", ans[i]);
return 0;
}复杂度
- 时间:链式跳跃求两侧斜率最大者,每个点被顶到的次数摊还为
,共 ; 单调栈两次扫描 ;沿 链递推每个点填一次, 。 总时间 。实测 时 C++ 约 0.1 s、Python 约 0.5 s(限时 1000 ms)。 - 空间:坐标、
、 、 、 各一个长度为 的数组, 。 C++ 静态数组约 20 MB,Python 约 120 MB(限时 256 MB,Python 侧需留意)。 - 正确性验证:与
暴力模拟在 3 万余组随机小数据(含大量三点共线、 全等高等对抗)上逐行比对, 分歧;随仓 10 组真实数据 C++ 与 Python 均全过。
总结
- 把几何问题翻译成斜率问题:本题最硬的一步是"能看到的最高山顶 = 斜率最大的点"。
它把"逐个检查可见性"的
判断,一次性换成"求斜率最大值"的结构化问题, 后面的数据结构才有用武之地。 - 善用摊还跳跃:求最优点不是凸包二分,而是"答案在已知点里就继续跳过去"
(
)。这种链式跳跃写起来比二分短,摊还复杂度还更好。 - "状态相同"是折叠模拟的关键:真正让模拟从
降到 的, 不是找规律,而是发现"在转向点 处的状态和以 为起点一模一样", 于是路径可以整段整段地合并成一条 链。 - 单调栈求"首个键更大的位置":这是可复用的小技巧,键可以是排序后的二元组, 只要压成整数就能直接进栈。
- 共线要靠严格不等号区分:把
<换成<=就会跳过被中间山顶挡住的情形, 数据里的共线链(problem4/problem5)专门打这种细节。