来自一个蒟蒻的求助
查看原帖
来自一个蒟蒻的求助
457666
Sity_Hugh楼主2022/8/17 12:37

求助!单调队列10分.....

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005; 
int n,m,res=2e9,t,w,r,sum,f[N],la[N],que[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>f[i]>>la[i];
	t=1;
	for (int l=1;l<=n;l++){
		sum-=f[l-1];
		if(que[t]==l-1) ++t;
		while (sum<m&&r<m){
			sum+=f[++r];
			while (t<=w&&la[r]>la[que[w]]) --w;
			que[++w]=r;
		}
		if (sum>=m) res=min(res,la[que[t]]);
	}
	cout<<res;
	return 0;
}
2022/8/17 12:37
加载中...