求助 ! #8 #9 TLE

GXZJQ @ 2024-01-03 13:00:20

#include<bits/stdc++.h>
using namespace std;
int n, k;
int num;
int s;
int ans1[1000001], ans2[1000001];
int len = 1;
int huanchun[1000001];
deque<int> mem;
int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> num;
        mem.push_back(num);
    }
    s = n - k + 1;//要移动的次数
    for (int i = 1; i <= s; i++) {
        int maxnum,minnum;
        for(int j=1;j<=k;j++){
            huanchun[j]=mem.front();
            mem.pop_front();
        }
        maxnum=huanchun[1],minnum=huanchun[1];
        for(int j=2;j<=k;j++){
            maxnum=max(huanchun[j],maxnum);
            minnum=min(huanchun[j],minnum);
        }
        ans1[len]=minnum;
        ans2[len]=maxnum;
        len++;
        for(int j=k;j>=2;j--){
            mem.push_front(huanchun[j]);
        }
    }
    for (int i = 1; i <= len - 1; i++) {
        cout << ans1[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= len - 1; i++) {
        cout << ans2[i] << " ";
    }
    return 0;
}

by heyx0201 @ 2024-01-03 13:20:53

@GXZJQ 时间复杂度最高是 k^2，这就是 TLE 的原因

by heyx0201 @ 2024-01-03 13:22:59

@GXZJQ 正解单调队列

by GXZJQ @ 2024-01-03 18:24:50

@heyx0201 谢谢 ， 已过

by kmlihaiming @ 2024-01-04 13:59:13

@heyx0201 逆天，这样能AC

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int n, k, minn = 1e9, maxx = -1e9, cnt = 1;

int main() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++)

        scanf("%d", &a[i]);

    for (int i = 1; i <= k; i++) {

        minn = min(minn, a[i]);
        maxx = max(maxx, a[i]);
    }

    b[1] = minn, c[1] = maxx;
    int l = 1, r = k;

    while (r <= n) {
        if (a[l] == minn || a[l] == maxx) {
            l++, r++, minn = 1e9, maxx = -1e9;

            for (int i = l; i <= r; i++) {

                minn = min(minn, a[i]);
                maxx = max(maxx, a[i]);
            }
        } else {
            l++, r++, minn = min(minn, a[r]), maxx = max(maxx, a[r]);
        }

        b[++cnt] = minn;
        c[cnt] = maxx;
    }

    for (int i = 1; i < cnt; i++)

        printf("%d ", b[i]);
    printf("\n");

    for (int i = 1; i < cnt; i++)

        printf("%d ", c[i]);
    return 0;
}

by heyx0201 @ 2024-01-04 21:38:57

@kmlihaiming 什么算法/yiw

by kmlihaiming @ 2024-01-05 13:25:22

@heyx0201 我也不清楚啊，就跟模拟很像，你可以看一下P3029这题，第一篇题解介绍了那个双指针two_pointer，跟尺取法很像，再加了一点优化就A了