70pts怎么优化

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

Ying_e @ 2024-03-16 14:31:29

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll maxx[20000005],minx[20000005],a[20000005];
int main()
{
    int n,m;
    cin >> n >> m;
    ll h=0,t=m;
    for(int i = 0;i<n;i++)
    {
        cin >> a[i];
    }
    ll maxi=0;
    while(t!=n+1)
    {
        maxx[maxi]=-20000005,minx[maxi]=20000005;
        if(maxi-1>=h&&maxi-1<=t&&a[t]<maxx[maxi])
        {
            maxx[maxi]=a[t];
            continue;
        }
        if(maxi-1>=h&&maxi-1<=t&&a[t]>minx[maxi])
        {
            minx[maxi]=a[t];
            continue;
            }//两个continue为了优化,判断上一个区间最大值与这个区间入队元素比较,最小值也是
        for(int i = h;i<t;i++)
        {

            if(a[i]>maxx[maxi]) maxx[maxi]=a[i];
            if(a[i]<minx[maxi]) minx[maxi]=a[i];
        }
        maxi++;
        h++;
        t++;

    }
    for(int i = 0;i<maxi;i++)
    {
        cout << minx[i]<<" ";
    }
    cout <<endl;
    for(int i = 0;i<maxi;i++)
    {
        cout << maxx[i]<<" ";
    }
    return 0;
}

by Ying_e @ 2024-03-16 14:56:49

好了90pts 但是#9超时


|