开始想用deque做,结果就得了 30pts ,后来提交了好几次之后竟然就这么 AC 了,
#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
const int MAXN=1e6+5;
struct tower
{
int h,v; //h:高度 v:能量值
int ans=0; //ans:接受的能量
};
int n;
tower t[MAXN];
deque <tower> que;
int ans=0;
int main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;++i)
cin>>t[i].h>>t[i].v;
que.push_back(t[1]);
for(int i=2;i<=n;++i)
{
while(que.size() && t[i].h>que.back().h)
{
t[i].ans+=que.back().v;
que.pop_back();
}
if(que.size())
que.back().ans+=t[i].v;
if(que.size() && que.back().ans>ans)
ans=que.back().ans;
que.push_back(t[i]);
if(que.back().ans>ans)
ans=que.back().ans;
}
cout<<ans;
return 0;
}