[C/C++] BOJ #1021 - Rotating Queues

The Baekjoon problem #1021 “Rotating Queue” involves using a deque to efficiently extract elements from specific positions. The goal of the problem is to calculate the minimum number of operations required to extract the desired elements in the given order. The term “operation” here refers to either rotating the deque one step to the left, one step to the right, or directly removing the first element from the deque.

---

First, the input consists of two integers, N and M, where N represents the total number of elements in the queue, and M represents the number of elements to be extracted. After that, M numbers are provided, representing the positions of the elements to be extracted. Initially, the queue contains numbers from 1 to N in sequential order.

 

To solve the problem, you must minimize the rotations required to extract the desired elements at specific positions. For each element to be extracted, you compare the number of steps required to rotate the deque to the left or right and choose the smaller of the two. The total number of operations is accumulated as you process each element.

 

In conclusion, the problem requires implementing logic to efficiently rotate the deque and select the optimal path for each operation. This involves updating the state of the deque iteratively and calculating the minimal number of operations required. The key is to find the most efficient way to update the deque while adhering to the constraints.

 

The “Rotating Queue” problem can be solved by understanding the properties of a queue. Given its simplicity, the problem’s 43% success rate is relatively decent for its difficulty level.

 

The rotating queue allows three operations:
1. Extracting the first element.
2. Rotating the deque one step to the left.
3. Rotating the deque one step to the right.

 

The objective is to minimize the use of operations 2 and 3 when extracting the desired numbers. While it might initially seem like an optimization problem, it is not particularly complex or algorithmically demanding.

 

I personally used an array-based approach.

 

Initially, I created an array of size N and initialized all positions to 0. Then, as I extracted elements, I marked the corresponding positions in the array with 1. For the next number to be extracted, I compared the current position with the target position to determine the faster direction. The results were accumulated and displayed.

---

Rotating queues

---

Below is the source code I wrote for this problem. Please consider it as a reference only.

//----------------------------------------------------------
//    baekjoon #1021 - Rotating Queue
//        - by Aubrey Choi
//        - created at 2019-09-22
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, s, c=1, t, ans=0;
    static char v[52];
    scanf("%d%d",&n,&m);
    for(int r=0;r<m;r++)
    {
        scanf("%d",&s);
        for(t=0;c!=s;c=c%n+1) t+=v[c]==0;
        ans += (t<n-r-t)?t:n-r-t; v[c]=1;
    }
    printf("%d\n", ans);
}