落谷过了,POJ却TLE
查看原帖
落谷过了,POJ却TLE
832996
xinruian楼主2023/10/20 21:24

代码如下,求大佬指点

#include <iostream>

using namespace std;

const int N = 1e6 + 5;

int a[N];
int q[N], hh, tt = -1;

int main() {
	ios::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++) {
		while (hh <= tt && q[hh] <= i - k)
			hh ++;
		while (hh <= tt && a[q[tt]] >= a[i]) 
			tt --;
		q[++ tt] = i;
		if (i >= k)
			cout <<a[q[hh]]  << ' ';
	}
	cout << endl;
	hh = 0, tt = -1;
	for (int i = 1; i <= n; i ++) {
		while (hh <= tt && q[hh] <= i - k)
			hh ++;
		while (hh <= tt && a[q[tt]] <= a[i]) 
			tt --;
		q[++ tt] = i;
		if (i >= k)
			cout << a[q[hh]] << ' ';
	}
	cout << endl;
	return 0;
}
2023/10/20 21:24
加载中...