csp试题2：学生排队

• • 题目
  • 分析
  • 代码
  • 总结

题目

问题描述

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

      例如，下面给出了一组移动的例子，例子中学生的人数为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，所有移动均合法。

分析

      因为每条指令包含学生id和移动change两个数据，所以创建了一个Instruction结构体。

      首先需要初始化学生初始队列。

      逐条指令对学生队列进行改变。首先在队列中找到该学生，然后依据指令判断是让其向前移动还是向后移动，然后对其进行移动。移动就是置换两个同学的位置。结束后执行下一条指令。

      输出最后的队列。

代码

/*
20190921
ccf试题2：学生排队 
*/ 

#include <iostream>
using namespace std;

struct Student{
	int id;
};

struct Instruction{
	int id;
	int change;
};

Student stu[1001];
Instruction instructions[1001];

int main(){
	//接收数据
	int n;
	cin >>n;
	int m;
	cin >>m;
	for(int i=0; i<m; i++){
		cin >>instructions[i].id;
		cin >>instructions[i].change;
	}	
	//初始队列
	for(int i=0; i<n; i++){
		stu[i].id = i+1;
	} 
	
	//处理每次的命令
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			if(stu[j].id == instructions[i].id){
				int index = j;
				int length = instructions[i].change;
				//进行前移 和 后移 
				if(length < 0){		//前移 
					length = 0 - length;
					for(int k=0; k<length; k++){
						Student temp = stu[index];
						stu[index] = stu[index-1];
						stu[index-1] = temp;
						index--;
					}
				}
				else{				//后移 
					for(int k=0; k<length; k++){
						Student temp = stu[index];
						stu[index] = stu[index+1];
						stu[index+1] = temp;
						index++;
					}
				}
				//已经移动结束，不能在判断之后的，因为有可能是后移 
				break;
			}
		} 
	} 
	
	//输出
	for(int i=0; i<n; i++){
		cout <<stu[i].id <<" ";
	} 
	return 0;
} 
           

总结

      解题思路很清晰，如果知道swap()函数的话，非常轻松。swap()很简单，代码如下：

void swap(int a, int b){
	int c = a;
	a = b;
	b = c;
}