链接: 模板题
数组模拟队列基本 *** 作
//在队尾插入元素 队友d出元素 int q[N],hh,tt = -1; //插入 q[++tt] = x; //d出 hh++ //判空 hh <= tt ? not empty : empty //队头 队尾 q[hh] q[tt]
#include#define fory(i,a,b) for(int i = a; i <= b; ++i) using namespace std; template inline void read(T& t) { int f = 0, c = getchar(); t = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) t = t * 10 + c - 48, c = getchar(); if (f) t = -t; } template void print(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) print(x / 10); putchar(x % 10 + 48); } const int N = 1e6 + 100; int n, k; int a[N], q[N]; int hh, tt; inline void minn() { hh = 0, tt = -1; fory(i, 0, n - 1) { if(hh <= tt && i - k + 1 > q[hh]) hh++; //判断是否队头滑出窗口 while(hh <= tt && a[q[tt]] >= a[i]) tt--; q[++tt] = i; if(i >= k - 1) print(a[q[hh]]), putchar(' '); } } inline void maxx() { hh = 0, tt = -1; fory(i, 0, n - 1) { if(hh <= tt && i - k + 1 > q[hh]) hh++; while(hh <= tt && a[q[tt]] <= a[i]) tt--; q[++tt] = i; if(i >= k - 1) print(a[q[hh]]), putchar(' '); } } signed main() { read(n), read(k); fory(i, 0, n - 1) read(a[i]); minn(); puts(""); maxx(); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)