双指针+ST表,50pts蒟蒻求助
查看原帖
双指针+ST表,50pts蒟蒻求助
797816
zshs_xhr楼主2023/12/16 10:25

改了几遍没找到错哪了, 思路:用ST存区间最小值,再用双指针找到和大于M的区间。

#include<bits/stdc++.h>
using namespace std;
const int M=100010;
long long n,m,f[M],s[M];
long long ma[M][21];
long long ans=0x3f3f3f3f;
int main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&f[i],&s[i]);
		ma[i][0]=s[i];
	}
	for(long long  j=1;j<=21;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
		}
	}
	for(long long l=1,r=0,sum=0;l<=n;){
		while(sum<=m&&r<n)sum+=f[++r];
		if(sum<m)break;
		long long k=log2(r-l+1);
		ans=min(ma[l][k],ma[r-(1<<k)+1][k]);
		sum-=f[l];
		l++;
	}
	printf("%lld",ans);
}

本人太弱了,有没有大佬帮个忙qwp

2023/12/16 10:25
加载中...