双向链表 倒数第二三个点TLE 求助
查看原帖
双向链表 倒数第二三个点TLE 求助
542472
R_I_C_K_Y_楼主2023/10/3 09:20
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
//定义
const int MAXN = 2e5 + 100;
struct Fruit{Fruit *Pre; Fruit *Next; int Start; int Length; int Divide;};
int N;

int main(){
    //输入
    scanf("%d",&N);
    //构建链表
    int Judge,Input;
    Fruit *Head = NULL; Fruit *Tail = NULL;
    for(int i = 1;i <= N;i ++){
        scanf("%d",&Input);
        if(i == 1){
            Judge = Input;
            Fruit *New = new Fruit;
            Tail = New; Head = New;
            New->Start = 1; New->Divide = Judge; New->Length = 1; New->Next = NULL; New->Pre = NULL;
        }
        else{
            if(Input == Judge) {Tail->Length++;}
            else{
                Judge = Input;
                Fruit *New = new Fruit;
                New->Pre = Tail;
                Tail->Next = New; Tail = New;
                New->Start = i; New->Divide = Judge; New->Length = 1; New->Next = NULL;
            }
        }
    }
    //处理
    Fruit *Point = Head;
   while(Head != NULL){
        while(Point != NULL){
            if(Point->Pre != NULL and Point->Pre->Divide == Point->Divide){//如果和前一个区块是同一种水果
                Point = Point->Next;//直接继续
                continue;
            }
            printf("%d ",Point->Start);//输出区块的第一个水果下标
            Point->Start ++;//第一个水果没了 下标向右1
            Point->Length --;//第一个水果没了 长度短1
            Point = Point->Next;
        }
        printf("\n");
        Point = Head;//回到头 重新开始
        while(Point != NULL){
            if(Point->Length <= 0){//如果这段水果拿完了
                if(Point->Pre == NULL and Point->Next != NULL) {
                    Head = Point->Next;//如果这是第一段 调整head
                    Head->Pre = NULL;
                }
                else if(Point->Pre != NULL and Point->Next != NULL){
                    Point->Next->Pre = Point->Pre;
                    Point->Pre->Next = Point->Next;
                }//不是第一段 且不是最后一段 将本段的上一段和下一段链接
                else if(Point->Pre != NULL and Point->Next == NULL){
                    Point->Pre->Next = NULL;
                }
                else if(Point->Pre == NULL and Point->Next == NULL){
                    for(int k = Point->Start;k < Point->Start + Point->Length;k ++) printf("%d\n",k);
                    return 0;
                }//如果是最后一段
            }
            Point = Point->Next;
        }
       Point = Head;//回到头 重新开始
    }
    return 0;
}
2023/10/3 09:20
加载中...