P1886 滑动窗口 /【模板】单调队列
思路
我们可以用单调队列解决这一问题,板子题。
代码
#include <bits/stdc++.h>
using namespace std;
struct FastIO {
template <typename T> FastIO& operator >> (T& in) {
in = 0;
char ch = getchar ();
int flag = 1;
for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') flag = -1;
for (; isdigit (ch); ch = getchar ()) in = (in << 3) + (in << 1) + (ch ^ 48);
in *= flag;
return *this;
}
}fin;
const int MaxN = 1e6 + 100;
int q1[MaxN], q2[MaxN], head1 = 1, head2 = 1, tail1 = 0, tail2 = 0;
int n, k;
int a[MaxN];
int ans[MaxN];
int main () {
fin >> n >> k;
for (int i = 1; i <= n; ++ i) fin >> a[i];
for (int i = 1; i <= n; ++ i) {
if (head1 <= tail1 && q1[head1] <= i - k) ++ head1;
if (head2 <= tail2 && q2[head2] <= i - k) ++ head2;
while (head1 <= tail1 && a[q1[tail1]] < a[i]) -- tail1;
while (head2 <= tail2 && a[q2[tail2]] > a[i]) -- tail2;
q1[++ tail1] = i;
q2[++ tail2] = i;
if (i >= k) printf ("%d ", a[q2[head2]]);
if (i >= k) ans[i] = a[q1[head1]];
}
putchar ('
');
for (int i = k; i <= n; ++ i) printf ("%d ", ans[i]);
putchar ('
');
return 0;
}
P1725 琪露诺
思路
通过模拟,发现类似于滑动窗口,于是使用单调队列+dp
代码
#include <bits/stdc++.h>
using namespace std;
struct FastIO {
template <typename T> FastIO& operator >> (T& in) {
in = 0;
char ch = getchar ();
int flag = 1;
for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') flag = -1;
for (; isdigit (ch); ch = getchar ()) in = (in << 3) + (in << 1) + (ch ^ 48);
in *= flag;
return *this;
}
}fin;
const int MaxN = 2e6 + 100;
int q[MaxN], head = 1, tail = 0;
int a[MaxN];
int dp[MaxN];
int n, l, r, k;
int main () {
fin >> n >> l >> r;
k = r - l + 1;
for (int i = 0; i <= n; ++ i) fin >> a[i];
memset (dp, -0x7f, sizeof (dp));
dp[0] = 0;
for (int i = 0; i <= n; ++ i) {
if (head <= tail && q[head] <= i - k) ++ head;
while (head <= tail && dp[q[tail]] < dp[i]) -- tail;
q[++ tail] = i;
dp[i + l] = dp[q[head]] + a[i + l];
}
int ans = -0x7fffffff;
for (int i = n + 1; i <= n + l; ++ i) ans = max (ans, dp[i]);
printf ("%d
", ans);
return 0;
}