我十分不理解!--RMQ党请注意
查看原帖
我十分不理解!--RMQ党请注意
723466
banned_gutongxing楼主2023/7/6 21:24

这道题一看就是一道RMQ裸题,但是。。。
就是WA 20

测试点信息
#1WA   #2WA
#3WA   #4WA
#5WA   #6WA
#7WA   #8AC
#9WA   #10AC

WHY????? 后来我看了一个讨论,心想他可能说得对,但是还是WA 20,DL们,到底是怎么了??
呈上本薛弱的代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int X = 100010;
int f[X][30],a[X],x,y;
int n,m;
int find(int l,int r){
	int x = (int)(log2(r-l+1));
	return min(f[l][x],f[r-(1<<x)+1][x]);
}
void RMQ(){
	for(int i = 1;i<=n;i++) f[i][0] = a[i]; 
	for(int j = 1;(1<<j)<=n;j++){
		for(int i = 1;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(f,INT_MAX,sizeof(f));
	cin >> n >> m;
	for(int i = 1;i<=n;i++) {
		cin >> a[i];
	}
	RMQ();
	for(int i = 1;i<=n-m+1;i++) {
		cout << find(i,i+4-1) << endl;
	}
	return 0;
}
2023/7/6 21:24
加载中...