【题解】发射站

题目来源：洛谷

题目描述

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

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

输入格式

第 1 行：一个整数 N;

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

输出格式

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

输入输出样例

输入 #1
3
4 2
3 5
6 10
输出 #1
7

数据范围

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

思路：

deque大法好

既可以队头队尾进出也可以队头队尾删除，多好啊！

拿样例来说，在做样例的过程中理解我的思路吧 ( ´･∀･｀)
样例（给他们加个id，就是编号，方便加能量）：

维护一个单调递减的序列

（4，2，1）
（3，5，2）
（6，10，3）

-（4,2,1）入队

q:(4,2,1)

-(3,5,2)准备入队

q:(4,2,1)。。。(3,5,2)

因为此时队尾的4比3高，所以3发射5个能量到编号1去

q:(4,2,1)(3,5,2)

-（6,10,3）准备入队

q:(4,2,1)(3,5,2)。。。（6,10,3）

因为队尾的3比6矮，所以3发射5个能量到编号3去，3弹出队尾

q:(4,2,1)。。。（6,10,3）

因为队尾的4比6矮，所以4发射2个能量到编号3去，4弹出队尾

q:(4,2,1)（6,10,3）

此时没有站可以入队了，刚刚收到能量最多的是编号3的6，收到了7个能量，分别来自编号1,2，over

code:

#include<bits/stdc++.h>
using namespace std;
int n;
long long f[1000010],anss;
struct node{
	int h,v,id;
}e;
deque <node> q;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&e.h,&e.v);
		e.id=i;
		while (!q.empty()&&q.back().h<e.h) 
        //此时的站点可以收到所有队尾比它矮的站点的能量，相当于题目所说的向右发射 
		{
			f[e.id]+=q.back().v;
			anss=max(anss,f[e.id]);
			q.pop_back();
			
		}
		if (!q.empty()&&q.back().h>e.h) //此时站点向左发射能量给离它最近的一个站点 
		  f[q.back().id]+=e.v,anss=max(anss,f[q.back().id]);
		q.push_back(e); //入队 
	}
	printf("%lld\n",anss); 
	return 0;
}

【题解】 发射站