THU2017spring 1-3 Interview 题解

THU2017spring 1-3 Interview


描述

某公司在对应聘者做过一轮笔试之后,从中选出n 人继续进行面试,每位应聘者被分配了一个整数ID。

为公平起见,组织者决定利用会议室外的圆桌,按以下方法“随机”确定面试顺序:第一个到达的应聘者在圆桌周围任意选择一个位置坐下;此后到达的每位应聘者都从前一应聘者出发,沿逆时针方向围圆桌走过m 人(前一应聘者算作走过的第1 人,同一人可能经过多次),并紧邻第m 人右侧就座;所有应聘者到齐后,从最后到达者出发,绕圆桌以顺时针方向为序进行面试。

这里假定应聘者到达的时刻互异,且相对的就坐位置确定后,左、右两人之间总能插入一把椅子。

试编写一个程序,确定面试顺序。

输入

共2行。

第1行包含两个整数, n和m。

第2行包含n个整数,表示先后到达的n个应聘者的ID。

输出

共1行。以空格分隔的n个整数,分别表示顺次进行面试的应聘者的ID。

输入样例

1
2
5 3
6 7 8 9 10

输出样例

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注