首页 > 试题广场 >

能量辐射

[编程题]能量辐射

热度指数：1095 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 某地有 $N$ 个能量发射站排成一行，每个发射站 $i$ 都有不相同的高度 $H_i$ ，并能向两边（两端的发射站只能向一边）同时发射能量值为 $V_i$ 的能量，发出的能量只被两边 最近的且比它高 的发射站接收。显然，每个发射站发来的能量有可能被 $0$ 或 $1$ 或 $2$ 个其他发射站所接受。

$\hspace{15pt}$ 请计算出接收最多能量的发射站接收的能量是多少。

输入描述:

输入的第  行包含一个整数 （），表示能量发射站的个数。

对于输入的第  到  行，第  行有两个整数 （）、（），表示第  个发射站的高度和发射的能量值。

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Yui___

单调栈

#include <iostream>
#include <vector>
#include <stack>

int main()
{
    int n = 0;
    std::cin>>n;

    std::vector<std::pair<int,int>> stations(n);
    for(int i = 0;i < n;++i)
    {
        auto&[a,b] = stations[i];
        std::cin>>a>>b;
    }

    std::stack<int> st;
    std::vector<int> nums(n);
    for(int i = 0;i < n;++i)
    {
        while(!st.empty() && stations[st.top()].first < stations[i].first)
        {
            nums[i] += stations[st.top()].second;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();

    for(int i = n-1;i >= 0;--i)
    {
        while(!st.empty() && stations[st.top()].first < stations[i].first)
        {
            nums[i] += stations[st.top()].second;
            st.pop();
        }
        st.push(i);

    }

    int ans = 0;
    for(int&num:nums)
    {
        ans = std::max(ans,num);
    }

    std::cout<<ans<<'\n';

}

发表于 2025-11-24 14:52:50 回复(0)