发射站

发射站

题目

【题目描述】

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

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

【输入格式】

第 1 行：一个整数 n;

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

【输出格式】

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

【数据规模】

对于 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。

解析

很水的一道单调栈题。

因为信号是同时向两边发射的,我们不妨将其拆成两部分,一部分为向左发射,一部分为向右发射;

先从左到右扫一遍,如果当前塔的高度比栈顶高,就将栈顶塔的v值加入当前塔的ans里,不断弹出直到栈空或栈顶比当前塔高即可；

之后再从右到左扫一遍,具体和之前一样；

最后在ans中找出最大的即可。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
struct rec{
    int h,v;
}stack[1000001],stack1[1000001];
int n,hi[1000001],vi[1000001],top=1,ans[1000001],maxn=-1;
int main()
{
    memset(ans,0,sizeof(ans));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>hi[i]>>vi[i];
        while(stack[top-1].h<hi[i]&&top>1)
        {
            ans[i]+=stack[top-1].v;
            top--;
        }
        stack[top].h=hi[i];
        stack[top].v=vi[i];
        top++;
    }
    top=1;
    for(int i=n;i>=1;i--)
    {
        while(stack1[top-1].h<hi[i]&&top>1)
        {
            ans[i]+=stack1[top-1].v;
            top--;
        }
        stack1[top].h=hi[i];
        stack1[top].v=vi[i];
        top++;
    }
    for(int i=1;i<=n;i++) maxn=max(maxn,ans[i]);
    cout<<maxn;
    return 0;
}

view code