Solutions CS101

Appearance

2 队列的应用 4题 ​

sy300: 队列的操作序列 简单 ​

https://sunnywhy.com/sfbj/7/2/300

现有一个空队列q，按顺序执行n个操作序列，每个操作是下面的两种之一：

  1. 让一个正整数k入队
  2. 让队首元素出队，同时将其输出

输入

第一行一个整数n（1≤n≤100），表示操作序列的个数；

接下来n行，每行一个操作序列，格式为以下两种之一，分别对应入队和出队的操作，其中push k表示需要将整数k（1≤k≤100）入队，而pop表示需要将队首元素出队：

  1. push k
  2. pop

输出

输出多行，每次出队时输出一行，表示出队的队首元素。如果无法出队，那么输出-1。

样例1

输入

8
push 2
pop
pop
push 5
push 3
push 6
pop
pop

输出

2
-1
5
3

解释

初始时队列为空，即[]。接下来进行以下8个操作：

  1. push 2：将2入栈，此时队列为[2]；
  2. pop：队首元素为2，因此输出2，出队后队列为[]；
  3. pop：由于队列为空，无法出队，因此输出-1；
  4. push 5：将5入队，此时队列为[5]；
  5. push 3：将3入队，此时队列为[5,3]；
  6. push 6：将6入队，此时队列为[5,3,6]；
  7. pop：队首元素为5，因此输出5，出队后队列为[3,6]；
  8. pop：队首元素为3，因此输出3，出队后队列为[6]。

The user is asking for a Python program that simulates a queue. The program should read a sequence of operations from the input, perform the operations on the queue, and print the result of each "pop" operation. If a "pop" operation is performed on an empty queue, the program should print "-1".

Here is a Python program that accomplishes this:

python
from collections import deque

def main():
    n = int(input().strip())
    queue = deque()

    for _ in range(n):
        operation = input().strip().split()
        if operation[0] == 'push':
            queue.append(int(operation[1]))
        elif operation[0] == 'pop':
            if queue:
                print(queue.popleft())
            else:
                print(-1)

if __name__ == "__main__":
    main()

In this program, we use a deque from the collections module to simulate a queue. The main function reads the number of operations from the input, then reads each operation. If the operation is "push", the program appends the number to the right end of the queue. If the operation is "pop", the program removes and prints the number from the left end of the queue. If the queue is empty when a "pop" operation is performed, the program prints "-1".

sy301: 求和队列 简单 ​

https://sunnywhy.com/sfbj/7/2/301

现有一个空队列q，按顺序将n个正整数a1、a2、...、an入队，接着反复执行操作：将队首的两个元素求和，并将结果入队。最后队列中将只剩下一个整数，将这个整数输出。

输入

第一行一个整数n（1≤n≤100），表示正整数的个数；

第二行为空格隔开的n个正整数a1、a2、...、an（1≤ai≤100）。

输出

输出一个整数，表示队列中剩下的整数。

样例1

输入

5
2 5 4 1 6

输出

18

解释

初始时队列为[2 5 4 1 6]。接下来进行以下操作：

  1. 计算2+5=7，并将7入队，当前队列为4 1 6 7；
  2. 计算4+1=5，并将5入队，当前队列为6 7 5；
  3. 计算6+7=13，并将13入队，当前队列为5 13；
  4. 计算5+13=18，并将18入队，当前队列为18，因此输出18；

The user is asking for a Python program that simulates a queue. The program should read a sequence of integers from the input, perform the operations on the queue (sum the first two elements and enqueue the result), and print the final result when only one element is left in the queue.

Here is a Python program that accomplishes this:

python
from collections import deque

def main():
    n = int(input().strip())
    numbers = list(map(int, input().strip().split()))
    queue = deque(numbers)

    while len(queue) > 1:
        a = queue.popleft()
        b = queue.popleft()
        queue.append(a + b)

    print(queue[0])

if __name__ == "__main__":
    main()

In this program, we use a deque from the collections module to simulate a queue. The main function reads the number of integers and the integers themselves from the input, then enqueues each integer. While there is more than one integer in the queue, the program removes and sums the first two integers, then enqueues the result. When only one integer is left in the queue, the program prints it.

sy302: 约瑟夫环-队列 简单 ​

https://sunnywhy.com/sfbj/7/2/302

约瑟夫环：假设n个人按编号顺时针从小到大排成一圈（编号为从1到n）。接着约定一个正整数，从编号为1的人开始顺时针报数（编号为1的人报数1，编号为2的人报数2……），报到的人离开圈子，然后他的下一个人继续从1开始报数，以此类推，直到圈子里只剩下一个人。

请用队列模拟约瑟夫环的报数过程，并按先后顺序输出离开圈子的人最开始的编号。为了统一起见，圈子里的最后一个人也需要离开圈子。

输入

两个整数n、k（1≤n≤100,1≤k≤100），含义如题意所示。

输出

输出n个整数，按先后顺序表示离开圈子的的人最开始的编号。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

6 3

输出

3 6 4 2 5 1

解释

一开始有6个人：1 2 3 4 5 6，从1号开始报数，报到3的人离开圈子。

第一轮：报号顺序为1->2->3，3号离开圈子，还剩下1 2 4 5 6，从4号开始报数；

第二轮：报号顺序为4->5->6，6号离开圈子，还剩下1 2 4 5，从1号开始报数；

第三轮：报号顺序为1->2->4，4号离开圈子，还剩下1 2 5，从5号开始报数；

第四轮：报号顺序为5->1->2，2号离开圈子，还剩下1 5，从5号开始报数；

第五轮：报号顺序为5->1->5，5号离开圈子，还剩下1，从1号开始报数；

第六轮：报号顺序为1->1->1，1号离开圈子，过程结束。

The user is asking for a Python program that simulates the Josephus problem using a queue. The program should read two integers n and k from the input, perform the operations on the queue (count k-1 people and remove the kth person), and print the original positions of the people in the order they are removed.

Here is a Python program that accomplishes this:

python
from collections import deque

def main():
    n, k = map(int, input().strip().split())
    queue = deque(range(1, n+1))

    while queue:
        queue.rotate(-(k-1))
        print(queue.popleft(), end=' ' if len(queue) != 0 else '\n')

if __name__ == "__main__":
    main()

Help on method_descriptor:

rotate(...) Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.

In this program, we use a deque from the collections module to simulate a queue. The main function reads the number of people and the count from the input, then enqueues each person's position. While there are still people in the queue, the program rotates the queue k-1 positions to the left, then removes and prints the person at the front of the queue. The rotation operation effectively moves the kth person to the front of the queue.

sy303: 匹配队列 简单 ​

https://sunnywhy.com/sfbj/7/2/303

现有两个队列q1、q2，假设q1、q2初始状态下均有个n元素，每个元素为1和2之一，且q1中元素1的个数与q2中元素1的个数相同、q1中元素2的个数与q2中元素2的个数也相同。

接下来循环执行下面的操作，直到两个队列均为空：

  1. 如果q1、q2的队首元素相同，那么将两个队列的队首元素出队；
  2. 否则，将q2的队首元素移至队尾。

问需要执行多少轮操作，才能达成停止条件。

输入

第一行一个整数n（1≤n≤100），表示正整数的个数；

第二行为空格隔开的n个正整数1或2，表示q1中从队首到队尾的所有元素；

第三行为空格隔开的n个正整数1或2，表示q2中从队首到队尾的所有元素。

输出

输出一个整数，表示需要执行的操作轮数。

样例1

输入

4
1 2 2 1
2 1 1 2

输出

6

解释

初始状态下：

：1 2 2 1 ：2 1 1 2

第一轮：

q1的队首元素为1，q2的队首元素为2，不相同，因此把q2的队首元素移至队尾，得到：

q1：1 2 2 1 q2：1 1 2 2

第二轮：

q1的队首元素为1，q2的队首元素为1，相同，因此把队首元素出队，得到：

q1：2 2 1 q2：1 2 2

第三轮：

q1的队首元素为2，q2的队首元素为1，不相同，因此把的队首元素移至队尾，得到：

q1：2 2 1 q2：2 2 1

第四轮：

q1的队首元素为2，q2的队首元素为2，相同，因此把队首元素出队，得到：

q1：2 1 q2：2 1

第五轮：

的队首元素为2，的队首元素为2，相同，因此把队首元素出队，得到：

：1 ：1

第六轮：

q1的队首元素为1，q2的队首元素为1，相同，因此把队首元素出队，得到：

q1：空 q2：空

因此共需要6轮操作。

The user is asking for a Python program that simulates two queues. The program should read two sequences of integers from the input, perform the operations on the queues (if the first elements of the two queues are the same, dequeue them; otherwise, move the first element of the second queue to its end), and print the number of operations until both queues are empty.

Here is a Python program that accomplishes this:

python
from collections import deque

def main():
    n = int(input().strip())
    q1 = deque(map(int, input().strip().split()))
    q2 = deque(map(int, input().strip().split()))

    count = 0
    while q1 and q2:
        if q1[0] == q2[0]:
            q1.popleft()
            q2.popleft()
        else:
            q2.append(q2.popleft())
        count += 1

    print(count)

if __name__ == "__main__":
    main()

In this program, we use a deque from the collections module to simulate a queue. The main function reads the number of integers and the integers themselves from the input, then enqueues each integer into the corresponding queue. While there are still integers in both queues, the program checks the first integer of each queue. If they are the same, the program removes them; otherwise, the program moves the first integer of the second queue to its end. The program counts the number of operations and prints it when both queues are empty.