题目描述

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 HiHi，并能向两边（当然两端的只能向一边）同时发射能量值为 ViVi 的能量，并且发出的能量只被两边最近的且比它高的发射站接收。

显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，出于安全考虑，每个发射站接收到的能量总和是我们很关心的问题。

由于数据很多，现在只需要你帮忙计算出接收最多能量的发射站接收的能量是多少。

输入格式
第一行包含整数N。

接下来N行，每行包含两个整数HiHi和ViVi，其中第 i 行的数据为第 i 个发射站的高度和能量值。

输出格式
输出仅一行，表示接收最多能量的发射站接收到的能量值。

数据保证答案不超过231−1231−1。

数据范围
1≤N≤1061≤N≤106,
1≤Hi≤2∗1091≤Hi≤2∗109,
1≤Vi≤10000

样例

输入样例：

3
4 2 
3 5 
6 10

输出样例：

7

开一个单调递减的栈,统计所有高度单调递减的发射站.
1. 如果当前这个数字破坏了单调递减,那么它会挡掉比它矮的所有发射站.
然后将所有比它能量小的发射站,统统吸取.然后将这些发射站出栈,自己入栈.
2. 如果当前发射站,满足单调递减的话,那么栈顶所属的发射站,吸取它的能量.同样自己也需要入栈

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1001000;
int a[N],b[N],s[N],res;
stack<pair<int,int>> p;

int main(){
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    p.push(make_pair(a[1],1));
    for(int i=2;i<=n;i++){
        while(p.size() && p.top().first < a[i]){
            s[i] += b[p.top().second];
            p.pop();
        }
        if(p.size()){
             s[p.top().second] += b[i];   //刚开始报错Segmentation Fault，应该是这里的原因，如果为空，栈顶指向未知元素不是0
        }
        p.push(make_pair(a[i],i));
    }
    for(int i=1;i<=n;i++){
        res = max(res,s[i]);
    }
    cout<<res<<endl;
    return 0;
}

另外还有一种思路就是可以跑两遍单调栈
从左到右开始扫的话保证我的能量只自来于左边高度比我低的能量塔
从右到左开始扫的话保证我的能量只自来于右边高度比我低的能量塔
代码可以去参考这位兄弟的
https://www.acwing.com/solution/acwing/content/1482/