[Baekjun, C++] 1966: printer Queue

 https://www.acmicpc.net/problem/1966


#include <iostream> #include <queue> using namespace std; int main() { int count = 0; int test_case; cin >> test_case; int n, m, ipt;//문서의 개수, 궁금한 문서 위치, 중요도 for (int i = 0; i < test_case; ++i) { count = 0; cin >> n >> m; queue<pair<int, int>> q; priority_queue<int> pq; // 우선순위 큐 for (int j = 0; j < n; ++j) { cin >> ipt; q.push({ j, ipt }); pq.push(ipt); } while (!q.empty()) { int index = q.front().first; int value = q.front().second; q.pop();//pop it so you can put it in the back if it's wrong if (pq.top() == value) {// if the value, which is the next in queue's priority matches the next priority pq.pop(); ++count; if (index == m) { cout << count << endl; break; } } else q.push({ index,value });//if it's now suppose to be printed yet, push it back into the very end } } cin >> n; }


The problem could be solved using two queues. One is a regular queue q that stores requests in the order they are received by the printer. The other is a priority queue pq that stores requests in high priority order. However, q is special in that it stores the index along with the priority in pairs. So, for each iteration, we check if the first element of q is the same as the top element of pq. If not, we move it to the back. If they are the same, we print the document. Time Complexity: O(N^2) * test_cases Space Complexity: O(N)

Comments

Post a Comment

Popular posts from this blog

[BaekJun, C++] 1018: Repainting a Chess Board

Image
  https://www.acmicpc.net/problem/1018 Problem Jimin found an M×N sized board in his mansion that is divided into MN unit squares. Some of these squares are painted black, while the rest are white. Jimin wants to cut the board into 8×8-sized chessboards. A chessboard must have alternating black and white squares. Specifically, each cell should be painted either black or white, and two squares sharing an edge must have different colors. Therefore, there are only two ways to color the chessboard. One has the top-left square white, and the other has it black. There is no guarantee that the board is already colored like a chessboard, so Jimin plans to cut it into 8×8 pieces and repaint some of the squares. Naturally, he can choose the 8×8 sections from anywhere. Your task is to write a program that calculates the minimum number of squares that Jimin needs to repaint. Input The first line contains two integers, N and M. N and M are natural numbers greater than or equal to 8 and less tha...
Read more

Binary Search: The Efficient Solution for Sorted Arrays

Image
Binary Search is a powerful algorithm that allows you to efficiently search for a target element within a sorted array. This algorithm works by repeatedly dividing the search space in half, which makes it an extremely efficient method for finding elements in large, ordered datasets. The Prerequisite: Sorted Array Before we dive into the details of Binary Search, it's important to understand that this algorithm can only be applied to sorted arrays. If the array is not sorted, Binary Search will not work correctly, and you may end up with incorrect results. The reason for this requirement is that Binary Search relies on the fact that the array is already in order. This allows the algorithm to make informed decisions about which half of the array to search next, based on the comparison between the target element and the middle element of the current search space. The Binary Search Algorithm The Binary Search algorithm follows these steps: 1. Initialize the search space: Set the lowe...
Read more

[BaekJun,C++]1929: finding primes

Image
  https://www.acmicpc.net/problem/1929 Problem: Write a program that prints all prime numbers between M and N, inclusive. Input: The natural numbers M and N are given on the first line, separated by a space. (1 ≤ M ≤ N ≤ 1,000,000) The input guarantees that there is at least one prime number between M and N. Output: Print the prime numbers in ascending order, one per line. #include < iostream > #include < cstdio > #include < algorithm > using namespace std; int m, n; int main(void) { cin >> m >> n; int size = n - m + 1; int* prime = new int[n + 1]; prime[1] = 0; for (int i = 2; i < n + 1; i++) { prime[i] = 1; } //eratostheneses sieve for (int i = 2; i < n + 1;i++) { if (prime[i] == 0) { continue;// continue, break } else { for (int j = i * 2; j < n + 1; j += i) { //you don't always have to incerase the index by 1 prime[j] = 0; } } ...
Read more