TLE了，这能怎么优化

zsenhe @ 2022-11-07 20:40:06

#include <iostream>
using namespace std;
const long long N = 1e7*3;
long long s[N];

long long q[N];
long long hh=0,tt=-1;

void handler(long long * s,int length,int k){
    for(int i=0;i<length;i++){
        if(i-k>q[hh]) hh++;
        long long anser = 1e7*3;
        for(int j=hh;j<=tt;j++) {
            anser = min(anser,s[q[j]]);
        }
        q[++tt] = i;
        cout << (anser==1e7*3?0:anser) << endl;
    }
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>s[i];
    handler(s,n,k);
    return 0;
}

by Xy_top @ 2022-11-07 20:43:34

@zsenhe 当然了，这题要用滑动窗口，不会的话可以用RMQ或者线段树

您的算法时间复杂度比较高，是O(nm)无法通过本题

by zsenhe @ 2022-11-07 20:57:18

@stdios 这是我尝试优化之后的代码，改进之后多AC了两个样例，还是有两个TLE，还有什么能优化的地方吗

#include <iostream>
using namespace std;
const long long N = 1e7*3;
long long s[N];

long long q[N];
long long hh=0,tt=-1;

void handler(long long * s,int length,int k){
    for(int i=0;i<length;i++){
        if(i-k>q[hh]) hh++;
        long long anser = 1e7*3;
        while(hh<=tt&&s[i]<=s[q[tt]]) tt--;
        cout << (i==0?0:s[q[hh]]) << endl;
        q[++tt] = i;
    }
}

int main(){
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>s[i];
    handler(s,n,k);
    return 0;
}

by simple_line @ 2022-11-07 21:09:06

@zsenhe 网络上搜单调队列

by zsenhe @ 2022-11-07 21:12:57

@simple_line 我改成printf和scanf就过了，上面用的是单调队列

by zsenhe @ 2022-11-07 21:14:02

#include <iostream>
using namespace std;
const int N = (1e7)*3;

int s[N],q[N],hh=0,tt=-1;

void handler(int * s,int length,int k){
    for(int i=0;i<length;i++){
        if(i-k>q[hh]) hh++;
        while(hh<=tt&&s[i]<=s[q[tt]]) tt--;
        printf("%d\n",i==0?0:s[q[hh]]);
        q[++tt] = i;
    }
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&s[i]);
    handler(s,n,k);
    return 0;
}

ac的代码

by Xy_top @ 2022-11-08 06:23:49

@zsenhe cout其实不慢，在主函数里加上这一句话：

ios::sync_with_srtdio(false);

cin cout比scanf printf还要快

但主要是cout的endl很慢很慢 所以不要用endl

如果想用cout输出换行，那么这样：

cout << "\n";

速度也直接起飞

by Xy_top @ 2022-11-08 06:24:55

@zsenhe 您这个数组怎么开到1e7\times 3？

看题目要求

by zsenhe @ 2022-11-08 12:38:49

@stdios 受教了

by T17371361045 @ 2022-11-21 14:56:23

@Xy_top 果然是endl

by Xy_top @ 2022-11-21 18:17:19

@T17371361045 这点小事儿就不要再@我了啦，我事情很多的啦！