60分,求解如何优化
查看原帖
60分,求解如何优化
948424
kszx_w楼主2023/9/26 19:42

有几个超时的,麻烦帮帮忙看看如何修改?

#include<iostream>
using namespace std;

struct Link{
    int prev,data,next;
    Link():prev(-1),data(-1),next(-1){}; //结点初始化
    Link(int a,int b,int c):prev(a),data(b),next(c){};
};
Link t[200003];
int tot=1,head=1; //计数 记录位置 //t记录头节点的位置
void append(int val){
    if(tot==1){
        t[tot]=Link(-1,val,-1);
    }else{
        t[tot]=Link(tot-1,val,-1);// 双链表
        t[tot-1].next=tot;
    }
    tot++;
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int m=0;
        cin>>m;
        append(m);
    }
    while(tot>1){
        int k=0,d=0,tir=0;//k存储位置,d存储数字 tir存储当前位置
        // 标记,第一个结点
        cout<<head<<" "; //head代表头节点位置
        d=t[head].data;
        tot--;
        tir=t[head].next;
        if(tir==-1) break; //说明是尾部结点;


        bool f=false;
        while(tir!=-1){ // 向后移动,l是移动的次数
            if(d==t[tir].data){  
                if(!f){
                    head=tir;f=true; //更换头结点位置
                }             
                k=tir;
                tir=t[tir].next;                             
            }else{
                tot--;
                cout<<tir<<" ";
                d=t[tir].data;

                if(t[tir].next!=-1){ //结点在中间
                    t[t[tir].prev].next=t[tir].next;                  
                }else{ //在尾部;
                    t[t[tir].prev].next=-1;
                }                                             
                tir=t[tir].next; //更新位置 
                if(k!=0) t[k].next=tir;  //更新结点位置                          
            }
        }
        cout<<endl;
    }
    return 0;
}
2023/9/26 19:42
加载中...