洛谷P1901发射站[NOI导刊]
1362+
作者：crxis 发布：2021-06-16 分类：栈
题目大意：n个发射站，高度为h能量为v，每个发射站只会给左右两边第一个比他高的发射站发送能量，请问接受能量最多的发射站接受了多少能量？
发射站
题目描述
某地有 $N$ 个能量发射站排成一行，每个发射站 $i$ 都有不相同的高度 $H_i$，并能向两边（两端的发射站只能向一边）同时发射能量值为 $V_i$ 的能量，发出的能量只被两边**最近的且比它高**的发射站接收。显然，每个发射站发来的能量有可能被 $0$ 或 $1$ 或 $2$ 个其他发射站所接受。
请计算出接收最多能量的发射站接收的能量是多少。
输入输出格式
输入格式
第 $1$ 行一个整数 $N$。
第 $2$ 到 $N+1$ 行，第 $i+1$ 行有两个整数 $H_i$ 和 $V_i$，表示第 $i$ 个人发射站的高度和发射的能量值。
输出格式
输出仅一行，表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。
输入输出样例
输入样例 #1
3
4 2
3 5
6 10
输出样例 #1
7说明
对于 $40\%$ 的数据，$1\le N\le 5000,1\le H_i\le 10^5,1\le V_i\le 10^4$。
对于 $70\%$ 的数据，$1\le N\le 10^5,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。
对于 $100\%$ 的数据，$1\le N\le 10^6,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。
解题思路
暴力查找n方超时，可以用单调栈优化：维护一个单独递减的栈，因为遇到一个高的，栈中所有发射站都无法像右边传递能量，只能传给这个高的发射站。至于向左边传递能量，因为单调递减，所以只需要传给栈顶就行。如果高度相等，合并他们，因为他们中间全是矮的可以忽略，他们向左右传递的能量目标是一样的。
程序实现
