牛客小Bai月赛52 D 环上食虫（尺取+st表）

登录—专业IT笔试面试备考平台_牛客网牛客网是互联网求职神器，C++、Java、前端、产品、运营技能学习/备考/求职题库，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://ac.nowcoder.com/acm/contest/11229/D很明显题目说明是一个环，所以数组开两倍，然后通过双指针尺取区间，用st表预处理掉奶油的区间最大，尺取的时候需要注意边界，r-l需要小于等于n，要不然就会出现吃空气的情况从而使答案出现错误。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define lowbit(x) ((x)&(-x))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
const int MAXN=1e6+5;
const int INF=0x3f3f3f3f;
const ll NNF=0x3f3f3f3f3f3f3f3f;


int n;
ll s;
ll a[MAXN];
ll st[MAXN][24];

ll query(int x,int y){
	int s=log2(y-x+1);
	return max(st[x][s],st[y-(1<<s)+1][s]);
}

void solve(){
	scanf("%d %lld",&n,&s);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	for(int i=1;i<=n;i++) scanf("%lld",&st[i][0]);
	for(int i=n+1;i<=2*n;i++){
		a[i]=a[i-n];
//		b[i]=b[i-n];
		st[i][0]=st[i-n][0];
	}
	for(int i=1;i<=23;i++){
		for(int j=1;j+(1<<i)-1<=2*n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
	int l,r;
	l=r=1;
	ll sum=0;
//	int mx=0;
	ll ans=INF;
	while(l<=r){
		while(r<=2*n&&sum<s){
//			mx=max(mx,a[r]);
			sum+=a[r++];
		}
		while(r-l>n){
			sum-=a[l++];
		}
		if(sum>=s){
			ll mx=query(l,r-1);
			ans=min(ans,mx);
		}else if(r>2*n) break;
		if(l<=r){
			sum-=a[l++];
		}
	}
	if(ans==INF) printf("-1");
	else printf("%lld",ans);
}


int main(){
	solve();
	return 0;
}