双向链表T了9个点怎么优化
查看原帖
双向链表T了9个点怎么优化
1377813
Luo_Saisei楼主2024/6/24 09:48

样例啥的都能过 一跑基本全T了

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data,num;
	node *pre,*nxt;
	bool used=0;
}; 
node *head,*p,*r,*m,*n;//把build——solve的指针和delete的指针分开 防止在删除中指针跑了 
int init_num,p_num;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

void build_list(int init_num)
{
	p_num=init_num;
	head= new node;
	r=head;
	for(int i=1;i<=init_num;i++)
	{
		p=new node;//申请新节点 
		p->data=read();
		p->num=i;
		p->pre=r;
		r->nxt=p;
		p->nxt=NULL; 
		r=p; 
	}
}
void solve_list()
{
	p=head;
	if(p->nxt->nxt==NULL) //就剩一个节点了
	{
		cout<<p->nxt->num;//猪鼻直接输出值就好
		p_num=0; 
	}
	else
	{
		while(p->nxt!=NULL)
		{
			if(p->data!=p->nxt->data)
			{
				p->nxt->used=1;//给这些byd用过的打上标记
				printf("%d ",p->nxt->num);
			}
			p=p->nxt;
		}
		printf("\n");
	} 
 } 
void delete_list()
{
	if(p_num) {
	m=head->nxt;
	while(m->nxt!=NULL)
	{
		if(m->used) 
		{
			m->pre->nxt=m->nxt;
			m->nxt->pre=m->pre;
			p_num--;//节点没咯 
		}
		m=m->nxt; 
	}
		if(m->used==1&&m->nxt==NULL) 
		{
			m->pre->nxt=m->nxt;
			p_num--;//节点没咯 
		}
	}
}
//void check_list()
//{
//	p=head->nxt;
//	while(p->nxt!=NULL)
//	{
//		cout<<p->num<<" "<<p->used<<endl;
//		p=p->nxt;
//	}
//	cout<<p->num<<" "<<p->used<<endl;
//}
int main()
{
	freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	scanf("%d",&init_num); 
	build_list(init_num);
	while(p_num)
	{
		solve_list();
		delete_list();
	}
//	check_list();
 } 
2024/6/24 09:48
加载中...