欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

艺术品构件堆叠问题

程序员文章站 2022-07-11 12:23:16
...

 

Dr.Kong设计了一件艺术品,该艺术品由N个构件堆叠而成,N个构件从高到低按层编号依次为1,2,……,N。艺术品展出后,引起了强烈的反映。Dr.Kong观察到,人们尤其对作品的高端部分评价甚多。

 

*的Dr.Kong一激动,对组成该艺术品的N个构件重新组合,比如:把第6层到第12层的构件搬下来,想一想,然后整体放到剩下构件的第7层下面;过一会儿,又把第2层到第9层的构件搬下来,整体放到剩下构件的第1层下面等等。于是,Dr.Kong在进行了连续若干次“搬来搬去”后,还是这N个构件,又诞生了一件新的艺术品。

 

编程:请输出新的艺术品最高十层构件的编号。

标准输入

第一行: N K 表示构件的总数和“搬来搬去”的总次数

2~K+1行:A B C 表示要搬动的构件(即从第A层到第B层)整个放在第C层下面;

如果C等于0,则要搬动的构件将放到最高层。

标准输出

由十行组成,分别为组成新艺术品的第一层到第十层构件的编号。

约束条件

1 10≤N≤20000 1≤k≤1000

(2) 1≤A≤B≤N, 0≤C≤N-(B-A+1)

样 例

 

标准输入

标准输出

13 3

6 12 1

2 9 0

10 13 8

 

6

7

8

9

10

11

12

2

3

4

 

代码:

建立链表,结构体里有编号和层数,每次移动,都将层数重新排列,全部移动完后输出移动后的编号,具体如下:


#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(floor)
int n=0;
struct floor
{
	int i; //层数
	int num; //编号
	floor *next;
};
struct floor *creat(int N) //创建链表
{
	struct floor *head;
	struct floor *p1,*p2;
	n=0;
	int t=1;
	p1=p2=(struct floor*)malloc(LEN);
	p1->i=t; p1->num=t;
	head=NULL;
	while(t<N)
	{
		n++; t++;
		if(n==1)head=p1;
		else p2->next=p1;
		p2=p1;
		p1=(struct floor *)malloc(LEN);
		p1->i=t;p1->num=t;
	}
	p2->next=NULL;
	return head;
}
void print(floor *head) //输出链表
{
	floor *p;
	p=head;
	int n=10;
	while(n--)
	{
		printf("%d\n",p->num); //输出编号
		p=p->next;
	}
}
struct floor *move1(floor *head,int a,int b,int c) //第一种情况
{
	floor *p,*pa,*pb,*pc,*pp; //将搬出的构件移动到上面
	p=head;
	while(p->i!=c&&p->next!=NULL) //查找c节点
		p=p->next;
	pc=p;
	while(p->i!=a&&p->next!=NULL) //查找a节点
	{
		pp=p; //记录a节点前面的节点
		p=p->next;
	}
	pa=p;
	while(p->i!=b&&p->next!=NULL) //查找b节点
		p=p->next;
	pb=p;
	pp->next=pb->next; //指针指向改变
	pb->next=pc->next; //从而改变顺序
	pc->next=pa;
	return head;
}
struct floor *move2(floor *head,int a,int b,int c) //第二种情况
{ //将搬出的构件移动到下面
	floor *p,*pa,*pb,*pc,*pp;
	p=head;
	while(p->i!=a&&p->next!=NULL)
	{
		pp=p; //记录a节点前面的节点
		p=p->next;
	}
	pa=p;
	while(p->i!=b&&p->next!=NULL)
		p=p->next;
	pb=p;
	if(c==0)
	{
		pp->next=pb->next;
		pb->next=head;
		head=pa;
		return head;
	}
	while(p->i!=c&&p->next!=NULL)
		p=p->next;
	pc=p;
	pp->next=pb->next; //指针指向改变
	pb->next=pc->next;
	pc->next=pa; //从而改变顺序
	return head;
}
struct floor *rank(floor *head) //对层数排序
{
	floor *p;
	p=head;int t=1; //每次移动后,将层数由高到低从1排序
	while(p!=NULL)
	{
		p->i=t;
		p=p->next;
		t++;
	}
	return head;
}
int main()
{
	int N,K;
	int a,b,c;
	struct floor *head;
	scanf("%d%d",&N,&K);
	head=creat(N);
	while(K--)
	{
		scanf("%d%d%d",&a,&b,&c);
		if(c<a&&c!=0) //将搬出的构件移动到上面
			head=move1(head,a,b,c);
		else if(c>b||c==0)
			head=move2(head,a,b,c);//将搬出的构件移动到下面
		head=rank(head); //,包括移动到最上面
	}
	print(head);
	return 0;
}

转载于:https://www.cnblogs.com/pcoda/archive/2011/07/01/2104551.html