运行不了，求调

wangyihao0411 @ 2024-07-07 10:03:48

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long a[100010],b1[100010],b2[100010];
queue<int> q;
queue<int> q1;
int main(){
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        while(!q.empty())
        {
            int t=q.front();
            if(t<k-i+1)
            {
                q.pop();
            }
            else
            {
                break;
            }
        }
        if(q.empty())
        {
            q.push(i);
        }
        int v=q.back();
        v=a[v];
        if(a[i]>v)
        {
            q.push(i);
        }
        else
        {
            while(!q.empty())
            {
                q.pop();
            }
            q.push(i);
        }
        b1[i]=q.front();
    }
    for(int i=1;i<=n;i++)
    {
        while(!q1.empty())
        {
            int t=q1.front();
            if(t<k-i+1)
            {
                q1.pop();
            }
            else
            {
                break;
            }
        }
        if(q1.empty())
        {
            q1.push(i);
        }
        int v=q.back();
        v=a[v];
        if(a[i]<v)
        {
            q1.push(i);
        }
        else
        {
            while(!q.empty())
            {
                q1.pop();
            }
            q1.push(i);
        }
        b2[i]=q1.front();
    }
    for(int i=1;i<=n-k+1;i++)
    {
        cout << b1[i] << " ";
    }
    for(int i=1;i<=n-k+1;i++)
    {
        cout << b2[i] << " ";
    }
    return 0;
}

by wangyihao0411 @ 2024-07-07 10:58:10

求调

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long a[100010],b1[100010],b2[100010];
queue<int> q;
queue<int> q1;
int main(){
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        while(!q.empty())
        {
            int t=q.front();
            if(t<i-k+1)
            {
                q.pop();
            }
            else
            {
                break;
            }
        }
        if(q.empty())
        {
            q.push(i);
        }
        else
        {
            int v=q.back();
            v=a[v];
            if(a[i]>v)
            {
                q.push(i);
            } 
            else
            {
                while(!q.empty())
                {
                    q.pop();
                    int v=q.back();
                    v=a[v];
                    if(a[i]>v)
                    {
                        q.push(i);
                        break;
                    }
                }
            }
        }
        cout << q.front() << "_ ";
        if(i>=k)
            b1[i-k+1]=a[q.front()];
    }
    for(int i=1;i<=n;i++)
    {
        while(!q1.empty())
        {
            int t=q1.front();
            if(t<i-k+1)
            {
                q1.pop();
            }
            else
            {
                break;
            }
        }
        if(q1.empty())
        {
            q1.push(i);
        }
        int v=q1.front();
        v=a[v];
        if(a[i]<v)
        {
            q1.push(i);
        }
        else
        {
            while(!q1.empty())
            {
                q1.pop();
                int v=q1.back();
                v=a[v];
                if(a[i]<v)
                {
                    q1.push(i);
                    break;
                }
            }
        }
        if(i>=k)
            b2[i-k+1]=a[q1.front()];
    }
    for(int i=1;i<=n-k+1;i++)
    {
        cout << b1[i] << " ";
    }
    cout << endl; 
    for(int i=1;i<=n-k+1;i++)
    {
        cout << b2[i] << " ";
    }
    return 0;
}

by huangshuchang @ 2024-07-07 13:11:12

@wangyihao0411 求关注

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,k;
struct node{
    int v,id;
}a[N];
deque<node> qmax;
deque<node> qmin;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i].v,a[i].id=i;
    for(int i=1;i<=n;i++){
        while(!qmin.empty()&&qmin.back().v>=a[i].v){
            qmin.pop_back();
        }
        qmin.push_back(a[i]);
        if(qmin.front().id<=i-k){
            qmin.pop_front();
        }
        if(i>=k){
            cout<<qmin.front().v<<" ";
        }
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        while(!qmax.empty()&&qmax.back().v<=a[i].v){
            qmax.pop_back();
        }
        qmax.push_back(a[i]);
        if(qmax.front().id<=i-k){
            qmax.pop_front();
        }
        if(i>=k){
            cout<<qmax.front().v<<" ";
        }
    }
    return 0;
}

by wangyihao0411 @ 2024-07-07 13:56:21

@huangshuchang 谢谢，已关