改了几遍没找到错哪了,
思路:用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