90分求调

Sean1221 @ 2024-07-10 10:08:24

#include<bits/stdc++.h>
using namespace std;
struct num
{
    int val,id;
    bool operator < (const num t) const
    {
        return val<t.val;
    }
};
struct num2
{
    int val,id;
    bool operator < (const num2 t) const
    {
        return val>t.val;
    }
};
int a[1000005];
priority_queue<num> q;
priority_queue<num2> q2;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for (int i=1;i<=k;i++)
    {
        scanf("%d",&a[i]);
        q2.push({a[i],i});
    }
    //cout<<q.size()<<endl;
    printf("%d ",q2.top().val);
    for (int i=k+1;i<=n;i++)
    {
        cin>>a[i];
        q2.push({a[i],i});
        while (!q2.empty()&&q2.top().id<=i-k)
        {
            q2.pop();
        }
        printf("%d ",q2.top().val);
    }
    printf("\n");
    for (int i=1;i<=k;i++)
    {
        q.push({a[i],i});
    }
    //cout<<q.size()<<endl;
    printf("%d ",q.top().val);
    for (int i=k+1;i<=n;i++)
    {
        q.push({a[i],i});
        while (!q.empty()&&q.top().id<=i-k)
        {
            q.pop();
        }
        printf("%d ",q.top().val);
    }
    return 0;
}

by BlackWuKong @ 2024-07-10 10:41:33

@Sean1221

#include<bits/stdc++.h>
using namespace std; 
struct Monotone_queue{
    static const int maxn=1000001;
    int n,k,a[maxn];
    int q[maxn],head,tail,p[maxn];
    void read(){
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
    }
    void monotone_max(){
        head=1;
        tail=0;
        for(int i=1;i<=n;++i){
            while(head<=tail&&q[tail]<=a[i])
                tail--;
            q[++tail]=a[i];
            p[tail]=i;
            while(p[head]<=i-k)
                head++;
            if(i>=k)printf("%d ",q[head]);
        }
        printf("\n");
    }
    void monotone_min(){
        head=1;
        tail=0;
        for(int i=1;i<=n;++i){
            while(head<=tail&&q[tail]>=a[i])
                tail--;
            q[++tail]=a[i];
            p[tail]=i;
            while(p[head]<=i-k)
                head++;
            if(i>=k)printf("%d ",q[head]);
        }
        printf("\n");

    }
}worker;
int main(){
    worker.read();
    worker.monotone_min();
    worker.monotone_max();
    return 0;
}

by BlackWuKong @ 2024-07-10 10:43:29

@Sean1221 求关

by Sean1221 @ 2024-07-10 10:43:51

@lanlingxuan

谢谢

by Sean1221 @ 2024-07-10 10:44:58

此贴结。

by Sean1221 @ 2024-07-10 10:47:30

@lanlingxuan OK