发射站(station) hgoi0527

发射站(station) hgoi0527 题解


题目描述

  • 某地的 N 个能量发射站排成一行,每个发射站 i,有互相不同高度 hi,并能向两边(端点处只能
    向一边)同时发射能量值为 vi 的能量,且发出的能量只能被两边最近的且比它高的发射站接收。
    显然,每个发射站发来的能量有可能被 0 至 2 个其它的发射站所接收。为了安全,我们关心每个
    发射站接收到的能量总和。由于数据很大,需要你计算出接收能量最多的发射站接收的能量是多少。

输入

  • 第 1 行:一个整数 N;
    每 2 到 N+1 行:每行有两个整数 hi 和 vi,表示第 i 个发射站的高度和发射的能量值。

输出

  • 只有一行,表示最多的能量值,答案不超过 32bit 的整数。

样例

  • 输入样例1
  • 3
    4 2
    3 5
    6 10
  • 输出样例1
  • 7
  • 数据规模
  • 对于 40%的数据,1<=N<=5000,1<=h<=100000,1<=v<=10000;
    对于 70%的数据,1<=N<=100000,1<=h<=2,000,000,000;1<=v<=10000;
    对于 100%的数据,1<=N<=1000000,1<=h<=2,000,000,000;1<=v<=10000。

题目解析

  • 非常玄妙的第一题,题目看了一会儿才看懂。
  • 因为每个杆子发射的信号只能被最近的比它高的杆子收到,显然,本题一定是通过扫一遍可以解决的。
  • 最容易想到的是使用单调队列,通过正一遍反一遍就可以得出来。
  • 稍加思考,我发现本题的单调队列只需要一边进出,故只是一个单调栈。同时稍微思考一下便可以将两次单调队列合二为一。程序并不繁琐,所以具体实现可以参考程序。

附上AC程序

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stack>
using namespace std;
typedef long long ll;
const ll LIMIT=1000010;
ll hei[LIMIT],val[LIMIT],res[LIMIT];
ll n;
void finit(){
    freopen("station.in","r",stdin);
    freopen("station.out","w",stdout);
}
stack<ll> stt;
int main(){
    #ifndef LOCAL
    finit();
    #endif
    scanf("%lld",&n);
    ll maxx=0;
    for (ll i=1;i<=n;i++){
        scanf("%lld%lld",&hei[i],&val[i]);
        ll tord=0;
        if (!stt.empty()){
            while (!stt.empty()&&hei[i]>=hei[tord=stt.top()]){
                if (hei[i]>hei[tord]) res[i]+=val[tord];
                stt.pop();
            }
        }
        if (!stt.empty()){
            res[tord]+=val[i];
            maxx=max(maxx,res[tord]);
        }
        stt.push(i);
        maxx=max(maxx,res[i]);
    }
    printf("%lld",maxx);
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注