CCF-CSP 学生排队

CCF-CSP 201703-2 学生排队 题解

问题描述

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
试题编号: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,所有移动均合法。

题解1

  这道题目思路比较简单,只要每次临时存储要移动的元素,然后考虑是向前移动还是向后移动。如果是向前移动q,则把这个元素前面的q个元素依次向后移动1位,然后再把这个元素放到空出来的那个位置即可。如果是向后移动q,则把这个元素后面的q个元素依次向前移动1位,然后再把这个元素放到空出来的那个位置即可。每次移动都按这个逻辑,最后输出结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input()) # 学生的数量
m = int(input()) # 调整的次数
L = list(range(1, n+1)) # 初始排队序列
lst = []
for _ in range(m):
i = list(map(int, input().split()))
index = L.index(i[0]) # 获取要移动的元素的当前索引
tmp = L[index] # 临时存储要移动的元素
if i[1] > 0: # 学生向后移,让他后面的|q|个学生依次向前移动1位
for j in range(index, index+i[1]):
L[j] = L[j+1]
else: # 学生向前移,让他前面的|q|个学生依次向后移动1位
for j in range(index, index-abs(i[1]), -1):
L[j] = L[j-1]
L[index+i[1]] = tmp # 要移动的学生,移动到指定位置
for i in L: # 输出结果
print(i, end=" ")

题解2

  还有一种方法是不需要考虑向前移动还是向后移动,把学生存储在 L 列表中,每次调整时,找出当前学生在列表中的下标,然后把该学生删掉,同时在列表末尾新增一个 0 元素。接着从后往前循环学生列表,到删除学生的下标 +1 为止,依次互换列表中的值,直到 0 元素到达删除的学生下标处;接着要做的就是把删除的学生号重新赋值进去 0 的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input()) # 学生的数量
m = int(input()) # 调整的次数
L = list(range(1, n + 1)) # 初始排队序列
for _ in range(m):
i = list(map(int, input().split()))
p = i[0] # 调整的学生
q = i[1] # 调整值
k = L.index(p) # 学生下标
k += q # 调整后的下标,这样就无需考虑正负
L.remove(p) # 学生暂时出列表
L.append(0) # 先填充0
for j in range(k + 1, n)[::-1]: # 从后往前,到删除学生的下标 +1 为止
L[j], L[j - 1] = L[j - 1], L[j] # 互换列表中的值
L[k] = p # 其他学生调整好以后,该学生到列表的指定位置
for i in L: # 输出结果
print(i, end=' ')
坚持原创技术分享,您的支持将鼓励我继续创作!