玄关!100pts,但是Unaccepted

P1886 滑动窗口 /【模板】单调队列

Dreeick @ 2024-02-05 23:08:22

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n,k,a[1000001],*maxi,*mini;
vector<int> ans;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    mini = min_element(a,a+k);
    maxi = max_element(a,a+k);
    cout << *mini << ' ';
    ans.push_back(*maxi);
    for(int i = 1,j = k+1;j <= n;i++,j++){
        if(mini-a == i-1) mini = min_element(a+i,a+j);
        else{
            if(a[j-1] < *mini) mini = a+j-1;
        }
        cout << *mini << ' ';
        if(maxi-a == i-1) maxi = max_element(a+i,a+j);
        else{
            if(a[j-1] > *maxi) maxi = a+j-1;
        }
        ans.push_back(*maxi);
    }
    cout << '\n';
    for(int i : ans){
        cout << i << ' ';
    }

    return 0; 
}

最后的点TLE了,不造为啥QWQ


by Stars_visitor_tyw @ 2024-02-06 00:08:44

@Dreeick 冷知识,min_element和max_element的时间复杂度最坏达到 O(n)n^2 不TLE就怪了


by Dreeick @ 2024-02-06 00:21:05

@taoyiwei17_cfynry emmm……看来代码得重写了

感谢DALAO


|