90分TLE求助

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

兩上星夢 @ 2021-01-02 18:57:59

萌新只有90分,第2个点tle了,能优化吗

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<queue>
using namespace std;

template<class T>void read(T& x)
{
    x = 0; int f = 0; char ch = getchar();
    while (ch < '0' || ch>'9') { f |= (ch == '-'); ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return;
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        priority_queue<pair<int, int>>a;
        vector<int>ans;
        for (int i = 0; i < k; i++)
            a.push({ nums[i],i });
        ans.push_back(a.top().first);
        for (int i = k; i < len; i++) {
            a.push({ nums[i],i });
            while (a.top().second <= i - k)
                a.pop();
            ans.push_back(a.top().first);
        }
        return ans;
    }
    vector<int> minSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>a;
        vector<int>ans;
        for (int i = 0; i < k; i++)
            a.push({ nums[i],i });
        ans.push_back(a.top().first);
        for (int i = k; i < len; i++) {
            a.push({ nums[i],i });
            while (a.top().second <= i - k)
                a.pop();
            ans.push_back(a.top().first);
        }
        return ans;
    }
    void print(vector<int>a) {
        for (int i = 0; i < a.size(); i++)
            printf("%d ", a[i]);
        printf("\n");
    }
};
Solution t;

void solve() {
    int n, k, num;
    read(n); read(k);
    vector<int> nums;
    for (int i = 1; i <= n; i++) {
        read(num);
        nums.push_back(num);
    }
    t.print(t.minSlidingWindow(nums, k));
    t.print(t.maxSlidingWindow(nums, k));
}

int main() {
    solve();
    return 0;
}

by bobbyyang @ 2021-01-08 21:06:39

优先队列第二个点卡常数

除非你手打优先队列加优化或者用O2

可以去用单调队列


by _MJawa_ @ 2021-01-24 17:11:40

开O2还真A了


by _MJawa_ @ 2021-01-24 17:13:15

另:priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>a;

您是怎么拿90的


|