用双指针和前缀和求Fk,用st表求区间最大值,不知道错在哪里,求大神帮忙看看。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,f[100005],s[100005][20];
ll ans = 1e18;
int main(){
cin >> n >> m;
for(int i = 1,v;i <= n;i++) {
cin >> v;
f[i] +=f[i-1] + v;
cin >> s[i][0];
}
for(int j = 1;j <=19;j++) {
for(int i = 1;i +(1<<j) -1 <= n;i++) {
s[i][j] = max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
}
}
int i {1},j {1};
while(j <= n) {
while(j <= n && f[j] - f[i-1] < m ) j++;
if(j > n) break;
int k = log2(j-i+1);
ans = min(ans,max(s[i][k],s[j-(1<<k)+1][k]));
//printf("i = %d,j = %d,ans = %lld\n",i,j,ans);
j++;
i = j;
}
cout << ans;
return 0;
}