自动搬运

查看原文

来自洛谷，原作者为

	ysj1173886760 **

搬运于2025-08-24 21:31:41，当前版本为作者最后更新于2018-08-08 19:00:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题和洛谷里这道题 P1823 十分相似。
做完这道题之后可以去做上面那道题。算是一个加强版吧。
这道题题意还是很明显的，我们维护一个单调栈即可。我们维护栈中的发射站高度的单调性。
栈中储存发射站的标号。我们将接收能量的过程分成两个阶段：
1.入栈时，由于栈是具有单调性的，如果栈顶的元素没有新加进来的元素高，那么他肯定就不能给后面的元素传输能量了，我们退掉这个元素，将新的元素加进来即可。
2.新的元素加进来以后，会对他在栈中下面那个元素传输能量，也就是离他最近还高于他的那个。P.S.（不需要对栈空时进行特判，我们只是对0这个元素传输了能量而已，最后不统计就行了）

那么确定思路以后，我们算法流程就是
for{
读入新元素
while(栈非空&&新元素高度大于栈顶元素高度)新元素能量加上栈顶元素能量，退栈； 栈顶元素能量加上新元素能量（对应第二种情况）
将新元素加入栈中
}
扫一遍传输能量的数组，找到max输出即可。

代码如下，就不加注释了，上面解释的很清楚了（很短吧）：

#include<iostream>
using namespace std;
const int maxn=1e6+10;
int s1[maxn],h[maxn],v[maxn],sum[maxn],ans,n,top;
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)
   {
   	cin>>h[i]>>v[i];
   	while(top&&h[s1[top]]<h[i])sum[i]+=v[s1[top--]];
   	sum[s1[top]]+=v[i];
   	s1[++top]=i;
   }
   for(int i=1;i<=n;i++)ans=max(ans,sum[i]);
   cout<<ans;
   return 0;
}