AcWing 599. 发射站
原题链接
简单
作者:
Ruccs
,
2021-01-03 20:11:17
,
所有人可见
,
阅读 416
/*
单调栈
首先这题的N也是很大
需要用数据结构来优化
用s[i]来记录这个塔的总能量
b[i]来记录这个塔原来的能量
a[i]来记录这个塔的高度
仰视奶牛那题满足的是单调递减的关系栈
这题也同样是这个样子
如果这个塔的高度大于栈顶的塔的高度
那么前面所有比它小的塔的能量b[i]都会被它吸走
知道栈顶的塔的高度大于当前这个塔结束
如果当前这个塔的高度小于栈顶的塔,那么它的能量会被栈顶吸收
*/
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
int n,a[N],b[N],s[N];
stack<pair<int,int>>q;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
}
q.push({a[1],1});
for(int i=2;i<=n;i++){
while(q.size()&&q.top().first<a[i])//当前比栈顶的高度高
{
s[i]+=b[q.top().second];
q.pop();
}
if(q.empty()) q.push({a[i],i});//特判如果出栈的结果是空,那么直接入栈
else{
s[q.top().second]+=b[i];
q.push({a[i],i});
}//否则得继续吸收能量
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,s[i]);
}
printf("%d\n",ans);
return 0;
}