CCF 201703-2 學生排隊||鏈表

來自專欄如何快速高效學習C++？1 人贊了文章- 計算機軟體能力認證考試系統?

118.190.20.162

試題編號： 201703-2

試題名稱： 學生排隊

時間限制： 1.0s

內存限制： 256.0MB

問題描述：

問題描述

　　體育老師小明要將自己班上的學生按順序排隊。他首先讓學生按學號從小到大的順序排成一排，學號小的排在前面，然後進行多次調整。一次調整小明可能讓一位同學出隊，向前或者向後移動一段距離後再插入隊列。

　　例如，下面給出了一組移動的例子，例子中學生的人數為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，所有移動均合法。

思路：用鏈表實現

#include <iostream>#include <vector>#if(__cplusplus==201103L)#include <unordered_map>#else#include <tr1/unordered_map>namespace std{ using std::tr1::unordered_map;}#endif#define test 0using namespace std;class node{public: int val=0; node*next=NULL; node*pre=NULL; node(int v){val=v;}};void adjust(unordered_map<int,node*>&map,int num,int change){ node*target=map[num]; target->pre->next=target->next; if(target->next)target->next->pre=target->pre; node*p=target; if(change>0){ for(int i=0;i<change;i++){ p=p->next; } }else{ for(int i=0;i>=change;i--){ p=p->pre; } } node*next=p->next; target->pre=p; p->next=target; target->next=next; if(next)next->pre=target;}node* build_list(int n,unordered_map<int,node*>&map){ node*head=new node(-1); node*p=head; for(int i=1;i<=n;i++){ p->next=new node(i); node* next=p->next; next->pre=p; p=next; map[i]=p; } p->next=NULL; return head;}void print_list(node*head){ node* p=head; cout<<endl; cout<<"Print List:"; while(p){ cout<<p->val<< ; p=p->next; } cout<<endl;}int main(){ int n=0,m=0; cin>>n>>m; unordered_map<int,node*>map; node*head=build_list(n,map);#if test print_list(head);#endif vector<vector<int> >arr(m); for(int i=0;i<m;i++){ int num=0,change=0; cin>>num>>change; arr[i].push_back(num); arr[i].push_back(change); } for(int i=0;i<(int)arr.size();i++){ adjust(map,arr[i][0],arr[i][1]);#if test print_list(head);#endif } node* p=head->next; while(p){ cout<<p->val; if(p->next)cout<< ; p=p->next; } cout<<endl; return 0;}

PS：