THU2017spring 1-3 Interview
描述
某公司在对应聘者做过一轮笔试之后，从中选出n 人继续进行面试，每位应聘者被分配了一个整数ID。
为公平起见，组织者决定利用会议室外的圆桌，按以下方法“随机”确定面试顺序：第一个到达的应聘者在圆桌周围任意选择一个位置坐下；此后到达的每位应聘者都从前一应聘者出发，沿逆时针方向围圆桌走过m 人（前一应聘者算作走过的第1 人，同一人可能经过多次），并紧邻第m 人右侧就座；所有应聘者到齐后，从最后到达者出发，绕圆桌以顺时针方向为序进行面试。
这里假定应聘者到达的时刻互异，且相对的就坐位置确定后，左、右两人之间总能插入一把椅子。
试编写一个程序，确定面试顺序。
输入
共2行。
第1行包含两个整数， n和m。
第2行包含n个整数，表示先后到达的n个应聘者的ID。
输出
共1行。以空格分隔的n个整数，分别表示顺次进行面试的应聘者的ID。
输入样例
5 3
6 7 8 9 10
输出样例
10 6 8 9 7
限制
1 ≤ n ≤ 10^3
1 ≤ m ≤ 2*n
输入的ID保证在int类型的范围内。
时间：1 sec
空间：256 MB
提示
一级提示
● 循环链表
二级提示
● 因为找座位按逆时针方向，面试按顺时针发现，所以建议使用双向循环链表。
● 往链表中插入元素时，要小心地修改前驱指针和后继指针。
● 一次性new n个节点，比分n次每次new一个节点快一些，但本题的数据规模不至于一定要这么做。
本题没用循环链表，数组即可，还省事。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include<iostream> #include<cstdio> #include<cstring> using namespace std; struct member{ int ID; int previous; int next; }; member * arr; void insertafterold(int old_ID,member & old,member & fresh,int fresh_ID){ fresh.previous=old_ID; fresh.next=old.next; arr[fresh.next].previous=fresh_ID; old.next=fresh_ID; } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; arr=new member[n+1]; int t; cin>>t; arr[1].ID=t; arr[1].previous=1; arr[1].next=1; for(int i=2;i<=n;i++){ int ID; cin>>ID; arr[i].ID=ID; int pos=i-1; for(int j=1;j<m;j++){ pos=arr[pos].next; } insertafterold(pos,arr[pos],arr[i],i); } bool flag=false; for(int i=n;!(i==n&&flag);i=arr[i].previous){ flag=true; cout<<arr[i].ID<<" "; } } |