分别用单调栈求每个发射站左右最近更高站，再把能量累加到对应接收站上。
OJ: luogu
题目 ID: P1901
难度:普及/提高-
标签:单调栈栈noip
日期: 2026-06-18 16:24
题意
给出 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;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的关键是把“左右最近更高站”识别成单调栈模型。
每个站只会被弹出一次，所以整套流程是线性的。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
