首页 > 代码库 > 6-1 移动的小球
6-1 移动的小球
你有一些小球，从左到右依次编号为1，2，3，…，n，
你可以执行两种指令。其中A X Y表示把小球X移动到小球Y左边，B X Y表示把小球X移动到小球Y右边。指令保证合法，即X不等于Y。
输入 小球个数n。指令条数m和m条指令，注意，1≤n≤500000，0≤m≤100000。
输出 从左到右输出最后的小球序列。
样例输入
6 2
A 1 4
B 3 5
样例输出
2 1 4 5 3 6
两种方法
代码1：
#include<stdio.h>const int MAXN=500000+10;int n,A[MAXN];int find(int x){ for(int i=1;i<=n;i++) if(A[i]==x) return i; return 0;}void shift_circular_left(int a,int b){ int t=A[a]; for(int i=a;i<b;i++) A[i]=A[i+1]; A[b]=t;}void shift_circular_right(int a,int b){ int t=A[b]; for(int i=b;i>a;i--) A[i]=A[i-1]; A[a]=t;}int main(){ int p,q,x,y,m; char type[9]; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) A[i]=i; for(int i=0;i<m;i++) { scanf("%s %d %d",&type,&x,&y); p=find(x); q=find(y); if(type[0]==‘A‘) { if(q>p) shift_circular_left(p,q-1); else shift_circular_right(q,p); } else { if(q>p) shift_circular_left(p,q); else shift_circular_right(q+1,p); } } for(int i=1;i<=n;i++) if(i==1) printf("%d",A[i]); else printf("%d",A[i]); printf("\n"); return 0;}
代码2：
#include<stdio.h>const int MAXN=1000;int n,left[MAXN],right[MAXN];void link(int X,int Y){ right[X]=Y; left[Y]=X;}int main(){ int i,m,X,Y,first=1; char type[9]; scanf("%d %d",&n,&m); right[0]=1; for(i=1;i<=n;i++) { left[i]=i-1; right[i]=i+1; } for(i=0;i<m;i++) { scanf("%s %d %d",&type,&X,&Y); link(left[X],right[X]); if(type[0]==‘A‘) { link(left[Y],X); link(X,Y); } else { link(X,right[Y]); link(Y,X); } } for(int X=right[0];X!=n+1;X=right[X]) if(first) { printf("%d",X); first=0; } else printf("%d",X); printf("\n"); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。