P1901 发射站

标签：head int P1901 1000001 tail 发射站

\(O(n)\)

#include<bits/stdc++.h>
using namespace std;
int n;
int q[1000001];
int f[1000001];
int a[1000001];
int b[1000001];
int head,tail;
int main()
{
	cin>>n;
	
	head=1;tail=0;
	
	for(int i=1; i<=n; i++)
	{
		cin>>a[i]>>b[i];
		
		while(head<=tail&&a[q[tail]]<a[i])
		{
			f[i]+=b[q[tail]];
			
			tail--;
		}
		
		f[q[tail]]+=b[i];
		
		q[++tail]=i;
	}
	
	int ans=0;
	
	for(int i=1; i<=n; i++)
	{
		ans=max(ans,f[i]);
	}
	
	cout<<ans<<endl;
}

标签：head,int,P1901,1000001,tail,发射站
From： https://www.cnblogs.com/dadidididi/p/16756078.html