大佬们，帮忙看一下，60分

imbecile @ 2021-10-03 00:33:07

#include<bits/stdc++.h>
using namespace std;    
int n,a[1000001],m,ma[1000001],mi[1000001]={100000};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i+m-1<=n;i++)
    {   
        ma[i]=0;
        mi[i]=10000; 
        for(int j=i;j<=i+m-1;j++)
        {
            if(a[j]>ma[i]) ma[i]=a[j];
            if(a[j]<mi[i]) mi[i]=a[j];
        }
    }
    for(int i=1;i+m-1<=n;i++) cout<<mi[i]<<" ";
    cout<<endl;
    for(int i=1;i+m-1<=n;i++) cout<<ma[i]<<" ";
} 

by yukimianyan @ 2021-10-03 00:56:19

楼主试图 \sout{O(n^2)} 过 \sout{10^6}

可以去学习一下单调队列再来做

by impuk @ 2021-10-03 01:00:32

你第一层循环算 n-m 次，你第二层循环算 m 次，那我 n 取 10^6，m 取 5\times10^5，你最里面那个

if(a[j]>ma[i]) ma[i]=a[j];
if(a[j]<mi[i]) mi[i]=a[j];

要执行 5\times10^{11} 次，电脑算不过来

by imbecile @ 2021-10-03 01:27:17

@yukimianyan 我是没学过 但就一个超时

by yukimianyan @ 2021-10-03 01:56:44

@zyxhty 只有一个超时又怎样，最多说明数据水，我帮你改了一下，只有 90 分，要避免超时需要另外的算法

by Qing_fy @ 2021-10-03 06:42:46

@zyxhty 1e6用O(n*n)肯定会T

by xieyikai2333 @ 2021-10-03 07:33:14

酱紫：

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int num,pos;
}a[1000005];
deque<node> minq,maxq;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].num),a[i].pos=i;
    for(int i=1;i<=n;i++)
    {
        while(!minq.empty()&&minq.back().num>=a[i].num)minq.pop_back();
        minq.push_back(a[i]);
        while(!minq.empty()&&minq.front().pos<=i-m)minq.pop_front();
        if(i>=m)printf("%d ",minq.front().num);
    }
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        while(!maxq.empty()&&maxq.back().num<=a[i].num)maxq.pop_back();
        maxq.push_back(a[i]);
        while(!maxq.empty()&&maxq.front().pos<=i-m)maxq.pop_front();
        if(i>=m)printf("%d ",maxq.front().num);
    }
    return 0;
}

这题是单调队列模板题

by _YUZIhaizhao_ @ 2021-10-03 07:36:55

看看这道题

#include<iostream>
#include<cstdio>
using namespace std;
int da[100000001],dl[100000001],id[100000001],le=1,ri;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>da[i];
    for(int i=1;i<=n;i++)
    {
        while(le<=ri&&da[i]<dl[ri])
            ri--;
        ri++; 
        dl[ri]=da[i];
        id[ri]=i;
        if(id[le]+k<=i)
            le++;
        if(i>=k)
            cout<<dl[le]<<" ";
    }
    le=1,ri=0;
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        while(le<=ri&&da[i]>dl[ri])
            ri--;
        ri++; 
        dl[ri]=da[i];
        id[ri]=i;
        if(id[le]+k<=i)
            le++;
        if(i>=k)
            cout<<dl[le]<<" ";
    }
}

by imbecile @ 2021-10-03 12:11:38

@yukimianyan 怎么改