90分re第二个点求调

ThChamp @ 2024-08-19 11:33:13

#include <iostream>
#include <deque>
using namespace std;

const int MAXN = 100000%;
int n, k, a[MAXN], s[MAXN]; 
deque<int> dq; // 求最大值，单调递减 求最小值，单调递增
void domax() {
    dq.clear();
    for (int i = 1; i <= n; i++) {
        if (dq.front() < i-k+1) // 队头滑出 
            dq.pop_front();
        while (!dq.empty() && a[i] >= a[dq.back()]) {
            dq.pop_back();
        } dq.push_back(i);
        if (i >= k)
            s[i-k+1] = dq.front();
    }
}

void domin() {
    for (int i = 1; i <= n; i++) {
        if (dq.front() < i-k+1) // 队头滑出 
            dq.pop_front();
        while (!dq.empty() && a[i] <= a[dq.back()]) {
            dq.pop_back();
        } dq.push_back(i);
        if (i >= k)
            s[i-k+1] = dq.front();
    }
}

int main() {
//  freopen("r.in", "r", stdin);
//  freopen("w.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    domin();
    for (int i = 1; i <= n-k+1; i++)
        cout << a[s[i]] << ' ';
    cout << endl;
    domax();
    for (int i = 1; i <= n-k+1; i++)
        cout << a[s[i]] << ' ';
    cout << endl;
    return 0;
}
/*
8 3
1 3 -1 -3 5 3 6 7

*/

by ydgly @ 2024-11-22 21:03:51

队头滑出前得判断队列是否为空

by EternalRights @ 2024-11-25 19:12:00

不需要那么复杂，第二种情况需要特判，第二种情况k == 1的时候，这种情况下l与r会失效。所以前排特判k == 1即可，具体可参考我的代码：

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = pair<int,int>;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n,k;
    cin >> n >> k;
    vector<int>v(n);
    vector<int>maxIndex(n - k + 1);
    int a = 0,b = 0;
    for ( int i = 0; i < n; i++){
        cin >> v[i];
        if ( i < k){
            a = v[a] > v[i] ? a : i;
            b = v[b] < v[i] ? b : i;
        }
    }
    if ( k == 1){
        for ( int i = 0; i < n; i++){
            cout << v[i] << " ";
        }
        cout << endl;
        for ( int i = 0; i < n; i++){
            cout << v[i] << " ";
        }
        return 0;
    }
    maxIndex[0] = a;
    cout << v[b] << " ";
    for ( int l = 1, r = k; r < n; l++,r++){
        if ( l - 1!= a && l - 1!= b){
            a = v[r] > v[a] ? r : a;
            b = v[r] < v[b] ? r : b;
        } else if ( l - 1 == a && l - 1 == b){
            a = v[r] > v[l] ? r : r - 1;
            b = v[r] < v[l] ? r : r - 1;
        } else if ( l - 1 == a){
            a = l;
            for ( int j = l; j <= r; j++){
                a = v[a] > v[j] ? a : j;
            }
            b = v[r] < v[b] ? r : b;
        } else if ( l - 1 == b){
            b = l;
            for ( int j = l; j <= r; j++){
                b = v[b] < v[j] ? b : j;
            }
            a = v[r] > v[a] ? r : a;
        }
        maxIndex[l] = a;
        cout << v[b] << " ";
    }
    cout << endl;
    for ( int i = 0; i < n - k + 1; i++){
        cout << v[maxIndex[i]] << " ";
    }

    return 0;
}