维护滚动数组,为啥最后一个点会TLE?
查看原帖
维护滚动数组,为啥最后一个点会TLE?
301200
bac0id楼主2020/11/3 14:29

O(nm)时间的方法都给过了,为啥这个O(n)会TLE呢?

#include <cstdio>
using namespace std;
int FastReadPos() {
	int x = 0;
	int c = getchar();
	while (c < '0' || c > '9') {
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x;
}
int n,m,min,sum,i,num;
int arr[3001];
int main() {
	n = FastReadPos();
	m = FastReadPos();
	arr[0] = FastReadPos();
	sum = arr[0];
	for (i = 1; i < m; ++i) {
		arr[i] = FastReadPos();
		sum += arr[i];
	}
	min = sum;
	for (i = m; i < n; ++i) {
		num = FastReadPos();
		//这里也试过单独维护填充指针来避免取模运算
		sum = sum + num - arr[i%m];
		arr[i%m] = num;
		if (sum < min) {
			min = sum;
		}
	}
	printf("%d",min);
	return 0;
}
2020/11/3 14:29
加载中...