萌新代码复杂度疑惑
查看原帖
萌新代码复杂度疑惑
339018
Panic_Kid楼主2021/10/27 11:16

蒟蒻感觉是n log n.... 上代码:

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

struct node{
    int pre;
    int tic;
};

node a[20005];
queue<node> q;

int main()
{
    node sb;
    sb.pre = -1;//设置断点
    int n;
    scanf("%d",&n);
    q.push(sb);
    for(int i = 1; i <= n;i++){
        scanf("%d",&a[i].pre);
        a[i].tic = i;
        q.push(a[i]);
    }
    

    int make = -1;
    int flag = n;
    while(n != 0){
        sb = q.front();
        if(sb.pre == -1){//一轮断点
            make = -1;
            q.pop();
            q.push(sb);
        }else if(make != sb.pre){//遇到最左边处理
            printf("%d ",sb.tic);
            make = sb.pre;
            q.pop();
            n -- ;
            flag --;
        }else{//不是跳过
            q.pop();
            q.push(sb);
            flag --;
        }

        if(flag == 0){//一轮结束换行
            printf("\n");
            flag = n;//队列的size(排除断点)
        }
    }
    return 0;
}
2021/10/27 11:16
加载中...