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;
}