问题描述

体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。

例如，下面给出了一组移动的例子，例子中学生的人数为8人。
　　0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；
　　1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；
　　2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；
　　3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
　　小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？

请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。

输入格式

输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。
　　第二行包含一个整数m，表示调整的次数。
　　接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。

输出格式

输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。

样例输入

8
3
3 2
8 -3
3 -2

样例输出

1 2 4 3 5 8 6 7

评测用例规模与规定

对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。

思路

看了看用例的规模，在1000以内，那么第一种想法就是直接用循环去进行插入和数组的移动，会有部分样例超出时间限制，第二种做法就是使用LinkedList类来对插入和删除元素进行处理，代码中最核心的就是通过输入所需要移动的学号与LinkedList类中的元素进行比较，如果两者相等，则得到下标值进行下面的操作，然后先移除所需要移动的元素，最后在最终移动的位置中添加刚刚删除的元素。

参考代码

import java.util.LinkedList;
import java.util.Scanner;

public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();//学生数量
	int m = scanner.nextInt();//调整的次数
	LinkedList<Integer>list = new LinkedList<Integer>();
	int[][] b = new int[m][2];//需要调整的学号以及移动的距离
	for(int i=0;i<m;i++){
		for(int j=0;j<2;j++){
			b[i][j]=scanner.nextInt();
		}
	}
	//初始化学生的学号
	for(int i=1;i<=n;i++){
		list.add(i);
	}
	int index=0;//索引
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(b[i][0]==list.get(j)){//得到当前位置i
				index=list.indexOf(list.get(j))+b[i][1];//移动的最终位置
				list.remove(list.get(j));//移除数值（先移除后添加）
				list.add(index,b[i][0]);//在需要的索引处添加刚刚移除的数值
				break;
			}
		}
	}
	for(int i=0;i<n;i++){
		System.out.print(list.get(i)+" ");
	}
}