60分求助
查看原帖
60分求助
890321
mooktian楼主2023/12/13 15:35

用双指针和前缀和求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;
}

2023/12/13 15:35
加载中...