2408727188GHR @ 2022-10-25 21:48:09
80分WA2和10求助!!!
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int n, k;
int a[maxn];
void qmax() {
int *q = new int[maxn], l = 0, r = 0;
memset(q, 0, sizeof(int) * maxn);
for (int i = 1; i <= n; i++) {
while (l < r && q[l] + k <= i)
l++;
while (l < r && a[q[r - 1]] < a[i])
r--;
q[r++] = i;
if (i >= k)
cout << a[q[l]] << " ";
}
delete[] q;
}
void qmin() {
int *q = new int[maxn], l = 0, r = 0;
memset(q, 0, sizeof(int) * maxn);
for (int i = 1; i <= n; i++) {
while (l < r && q[l] + k <= i)
l++;
while (l < r && a[q[r - 1]] > a[i])
r--;
q[r++] = i;
if (i >= k)
cout << a[q[l]] << " ";
}
delete[] q;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
qmin();
cout << endl;
qmax();
}
by _9192631770_ @ 2022-12-26 14:33:03
第三行maxn再大一些就可以了