分别用单调栈求每个发射站左右最近更高站，再把能量累加到对应接收站上。
OJ: luogu
题目 ID: P1901
难度:普及
标签:单调栈栈noip
创建: 2026-06-18 16:24
更新: 2026-10-07 12:15
后置题目
roj 3048「City Game」 城市游戏A 教的「入栈时弹掉违规元素、再看栈顶/新栈顶得到左侧最近合法元素」这一步被 B 搬进直方图单调栈：仅把比较方向从更高换成更矮，用弹出后的新栈顶当矩形左边界，再叠加 A 未教的按底边分组与悬垂高度递推。roj 10003牛牛的滑动窗口B 的 max 栈（弹出条件 top<=x、栈内值严格递减、存下标）就是 A 教的那一步：从左到右扫描并维护高度严格递减的单调栈、栈顶即往左最近的更大站；B 把同一个栈从「取最近更高站」转用为「左端点左移时的极值变化点」，再叠加 min 栈归并、按窗口长度差分入账与值域 100 的段数界这些 A 未涉及的新流程。luogu P7167[eJOI 2020] Fountain (Day1)B 用 A 的递减单调栈步骤求出每个圆盘下方第一个更大者的 nxt 链，再叠加倍增跳链扣容量
题意
给出 n 个排成一行的发射站，每个站有互不相同的高度 h 和能量 v。
每个站的能量会分别传给左右两边“最近的更高站”。
要求统计所有站接收到的总能量，输出其中最大值。
思路
先看最直接的做法：对每个站分别往左、往右暴力找最近更高站。
这个版本最容易理解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 对每个发射站直接向左右两边暴力寻找最近的更高站。
const int MAXN = 1000000 + 5;
int n;
long long h[MAXN], v[MAXN];
long long rec[MAXN]; // rec[i] 表示第 i 个发射站收到的总能量
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i] >> v[i];
}
for (int i = 1; i <= n; i++) {
// 向左暴力找最近的更高站。
int j = i - 1;
while (j >= 1 && h[j] < h[i]) {
j--;
}
if (j >= 1) {
rec[j] += v[i];
}
// 向右暴力找最近的更高站。
j = i + 1;
while (j <= n && h[j] < h[i]) {
j++;
}
if (j <= n) {
rec[j] += v[i];
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, rec[i]);
}
cout << ans << '\n';
return 0;
}它要对每个站都向左右暴力扫描，最坏会退化到 n=10^6。
注意“最近更高站”就是单调栈的经典应用。
左边最近更高站
从左到右扫描，栈里维护高度严格递减的站编号。
处理站 i 时：
- 先把栈顶所有高度小于
h[i]的站弹掉； - 如果栈不空，栈顶就是
i左边最近的更高站； - 把
i入栈。
右边最近更高站
再从右到左做一遍完全对称的扫描，就能找到右边最近更高站。
这样每个站只会进栈、出栈各一次。两次扫描结束后，把每个站的能量加到左右两个接收站上，最后在所有接收值中取最大值即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000 + 5;
int n;
long long h[MAXN], v[MAXN];
long long rec[MAXN]; // rec[i] 表示第 i 个发射站最终收到的总能量
int st[MAXN]; // 手写栈，保存可能成为“最近更高站”的位置
int top_pos;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i] >> v[i];
}
// 从左到右，求每个点左边最近的更高站。
top_pos = 0;
for (int i = 1; i <= n; i++) {
while (top_pos > 0 && h[st[top_pos]] < h[i]) {
top_pos--;
}
if (top_pos > 0) {
rec[st[top_pos]] += v[i];
}
st[++top_pos] = i;
}
// 从右到左，求每个点右边最近的更高站。
top_pos = 0;
for (int i = n; i >= 1; i--) {
while (top_pos > 0 && h[st[top_pos]] < h[i]) {
top_pos--;
}
if (top_pos > 0) {
rec[st[top_pos]] += v[i];
}
st[++top_pos] = i;
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, rec[i]);
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的关键是把“左右最近更高站”识别成单调栈模型。
每个站只会被弹出一次，所以整套流程是线性的。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
