o(nlog(n))的做法，几乎全RE

yiwugougou @ 2024-12-02 20:29:29

by GeorgeDeng @ 2024-12-03 20:42:29

你确定这个代码是 O(n \log n) 的做法吗？

不是 O(n^2 \log n) 吗？

by GeorgeDeng @ 2024-12-03 21:31:56

#include <bits/stdc++.h>
using namespace std;

int arr[1000005];
int n,k;
int minn = 0x3f3f,maxx = -0x3f3f;
int ansmin[1000005],ansmax[1000005];
int minp = 1,maxp = 1;
signed main()
{
    int top = 1;
    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        minn = min(minn,arr[i]);
        maxx = max(maxx,arr[i]);
        if(maxx==arr[i]){
            maxp = i;
        }
        if(minn==arr[i]){
            minp = i;
        } 
        if(i>=k){
            ansmin[top] = minn;
            ansmax[top] = maxx;
            top++;
            if(minp==(i-k+1)){
                //minn = a[i-k+2];
                minn = 0x7fffffff;
                for(int j = i-k+2;j<=i;j++){
                    minn = min(minn,arr[j]);
                    if(minn==arr[j]){
                        minp = j;
                    }
                }
            }
            if(maxp==(i-k+1)){
                //minn = a[i-k+2];
                maxx = -2147483648;
                for(int j = i-k+2;j<=i;j++){
                    maxx = max(maxx,arr[j]);
                    if(maxx==arr[j]){
                        maxp = j;
                    }
                }
            }
        }
    }
    for(int i = 1;i<top;i++){
        cout<<ansmin[i]<<' ';
    }
    cout<<endl;
    for(int i = 1;i<top;i++){
        cout<<ansmax[i]<<' ';
    } 
    return 0;
}

这样能 A。

你竟然不用单调队列，用卡常！

by GeorgeDeng @ 2024-12-03 21:32:08

@yiwugougou

by yiwugougou @ 2024-12-04 21:16:19

卡常怎么你啦

by yiwugougou @ 2024-12-04 21:18:02

@GeorgeDeng

by GeorgeDeng @ 2024-12-05 18:04:25

建议使用单调队列。

毕竟单调队列是 O(n) 的时间复杂度。

by GeorgeDeng @ 2024-12-05 18:04:41

@yiwugougou

by yiwugougou @ 2024-12-07 08:04:54

但卡常没TLE啊