---
title: "发射站"
created: 2025-11-28
tags:
  - 算法
---

# 发射站

## 题目 [发射站](https://www.acwing.com/problem/content/description/601/)

![[image-f654c015.png]]

## 思路分析

![[image-46488762.png]]

是每根柱子发送的信号只能被最近的比它高的接收到

而不是 每根柱子只能接收到最近的比它矮的

也就是说 一根较高的柱子可能接收多个信号

比如上图的高度为6的柱子 可以接收高度为4的柱子的2和高度为3柱子的5 一共得7

也就是说 在单调栈里面 不止是栈头是答案

而是单调栈里面所有小于当前柱子的都要累加起来

这个过程可以并在出栈里面 出栈时就res[i]+=

当然 还得累加一遍右边的

所以就是左右都做一遍单调栈 然后出现往上趋势出栈，同时累加答案

最后对答案数组求一个最大值即可

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

int h[N],v[N],ans[N];

int stk[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>h[i]>>v[i];

    }

    int top=0;

    for(int i=1;i<=n;i++){

        //找左边比它矮的数 所以出现往上趋势就出栈

        while(top && h[stk[top]]<h[i]){

            ans[i]+=v[stk[top]];

            top--;

        }

        stk[++top]=i;

    }

    top=0;

    for(int i=n;i>=1;i--){

        while(top && h[stk[top]]<h[i]){

            ans[i]+=v[stk[top]];

            top--;

        }

        stk[++top]=i;

    }

    int res=0;

    for(int i=1;i<=n;i++){

        res=max(res,ans[i]);

    }

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调栈/单调栈|单调栈]] 🏠 [[00-刷题理模型]] ➡️ [[城市游戏|城市游戏]]