题解 P1901 【发射站】

dqtr03 · 2018-09-03 23:31:48 · 题解

楼上的大神写的都是单调栈balabala的...

可能是我比较蒟蒻吧，只能想到双向链表这种低级数据结构

题目中说

发出的能量只被两边最近的且比它高的发射站接收

我们把它简化一下

如果一个地方发了洪水，那么水会随着时间不断涨高

当一个地方淹没的时候，其左右两边的仍然没有被淹没的地方就是题中所说的那两个发射站

那么我们就可以将每个点被淹没的时间排序，用双端链表来维护每个点的左右两边没被淹没的点

淹没时进行的操作就是把这个点从链表里删除，把自己的能量发射给左右，然后更新答案

具体代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long ll;
struct node1{int i;ll h;}P[1000050];
struct node{int Front,Next;ll v,k;}t[1000050];
bool cmp(node1 a,node1 b)
{
    return a.h<b.h;
}
ll ans=0;
inline void Del(int o)
{
    ans=max(ans,t[o].k);
    t[t[o].Front].k+=t[o].v;
    t[t[o].Next].k+=t[o].v;
    t[t[o].Front].Next=t[o].Next;
    t[t[o].Next].Front=t[o].Front;
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&P[i].h,&t[i].v);
        P[i].i=i;
        t[i].Front=i-1;//链表初始化 
        t[i].Next=i+1;
        t[i].k=0;
    }
    sort(P+1,P+n+1,cmp);//针对淹没时间(高度)排序 
    for(int i=1;i<=n;++i)Del(P[i].i);//淹没每个点 
    cout<<ans;
    return 0;
}