CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
单调队列模板题，求 n 个数每 k 个连续的数的最小最大值；最大值可直接插相反数进去，取出的时候再取回即可。
poj 上 STL 特别的慢了，语言要选 C++而非 G++才能勉强跑过…大致能看个做法即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <deque>
using namespace std;
const int N = 1e6 + 9;
typedef int ll;
typedef pair<ll, int> pli;
struct Monotone : deque<pli>
{
void push(const pli &p, int k)
{
while (!empty() && back().first >= p.first)
pop_back();
for (push_back(p); p.second - front().second >= k;)
pop_front();
}
} q[2];
int n, k, ans[2][N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0, a; i < n; ++i)
{
scanf("%d", &a);
q[0].push(pli(a, i), k);
ans[0][i] = q[0].front().first;
q[1].push(pli(-a, i), k);
ans[1][i] = -q[1].front().first;
}
for (int j = 0; j < 2; ++j)
for (int i = k - 1; i < n; ++i)
printf("%d%c", ans[j][i], i + 1 == n ? '\n' : ' ');
}
用数组模拟 STL 队列后直接快了一倍多…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <deque>
using namespace std;
const int N = 1e6 + 9;
typedef int ll;
typedef pair<ll, int> pli;
template <typename pli, size_t N>
struct WuKQueue
{
pli q[N];
int b, e;
WuKQueue() : b(0), e(0) {}
bool empty() const { return b == e; }
pli back() const { return q[e - 1]; }
pli front() const { return q[b]; }
void pop_front() { ++b; }
void pop_back() { --e; }
void push_back(pli p) { q[e++] = p; }
};
struct Monotone : WuKQueue<pli, N>
{
void push(const pli &p, int k)
{
while (!empty() && back().first >= p.first)
pop_back();
for (push_back(p); p.second - front().second >= k;)
pop_front();
}
} q[2];
int n, k, ans[2][N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0, a; i < n; ++i)
{
scanf("%d", &a);
q[0].push(pli(a, i), k);
ans[0][i] = q[0].front().first;
q[1].push(pli(-a, i), k);
ans[1][i] = -q[1].front().first;
}
for (int j = 0; j < 2; ++j)
for (int i = k - 1; i < n; ++i)
printf("%d%c", ans[j][i], i + 1 == n ? '\n' : ' ');
}