P1901 发射站

题目描述：

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

显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安 全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。

输入格式：

第 1 行：一个整数 N;

第 2 到 N+1 行：第 i+1 行有两个整数 Hi 和 Vi，表示第 i 个人发射站的高度和发射的能量值。

输出格式：

输出仅一行，表示接收最多能量的发射站接收到的能量值，答案不超过 longint。

输入样例：

1
2
3
4
3
4 2 
3 5 
6 10

输出样例：

1
7

说明/提示：

对于 40%的数据，1<=N<=5000；1<=Hi<=100000；1<=Vi<=10000;

对于 70%的数据，1<=N<=100000；1<=Hi<=2,000,000,000；1<=Vi<=10000;

对于 100%的数据，1<=N<=1000000;1<=Hi<=2,000,000,000；1<=Vi<=10000。

题目解析：

题目中有一句至关重要的话：发出的能量只被两边最近的且比 它高的发射站接收。

这句话揭露了解法：使用单调栈。

将题目精简下，留其核心就是要分别求每个数左边和右边碰到的第一个比它大的数的位置。

这是经典的单调栈可以解决的问题，所以直接写两个单调栈：一个求左边的位置，一个求右边的位置，找到位置后将其能量值存起来，在其中找一个最大值即可。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
 * @Date: 2019-09-05 21:32:02
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-05 23:10:34
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;

const int MAXN = 1000010;

LL arr[MAXN],s[MAXN],sum[MAXN],N,ans = -1;
stack<LL> stk;
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%lld",&N);
    arr[0] = 2000000100;
    arr[N+1] = 2000000100;
    for(int i = 1; i <= N; i++){
        scanf("%lld%lld",&arr[i],&s[i]);
    }
    //找一个数左右两边离该数最近的并且比该数大的数的位置
    
    //单调递减栈。 找当前数的右边目标数
    for(int i = 1; i <= N+1; i++){
        //找到了比当前栈顶大的数，更新值
        while(stk.size() && arr[i] > arr[stk.top()]){
            sum[i] += s[stk.top()];
            stk.pop();
        }
        stk.push(i);
    }
    stk.pop();
    

    //单调递减栈。 找当前数的左边目标数
    for(int i = N; i >= 0; i--){
        //找到了比当前栈顶大的数，更新值
        while(stk.size() && arr[i] > arr[stk.top()]){
            sum[i] += s[stk.top()];
            stk.pop();
        }
        stk.push(i);
    }
    stk.pop();
    for(int i = 1; i <= N; i++) ans = max(ans,sum[i]);
    printf("%lld",ans);
    return 0;
}