c421 - pA 雲端列印

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個雲端列印服務，根據客戶的優先權將列印工作分配給不同的印表機。優先權高的工作由優先印表機列印，優先權低的工作由普通印表機列印。輸入包含工作新增、優先印表機空閒和普通印表機空閒的指令，要求輸出列印工作的優先權順序。

解題思路

這題的核心在於模擬印表機的列印過程。使用一個 multiset 來儲存等待列印的工作優先權。multiset 能夠自動排序，並且允許儲存重複的優先權。當收到優先印表機空閒的指令 (-2) 時，取出 multiset 中優先權最高的元素並輸出。當收到普通印表機空閒的指令 (-1) 時，取出 multiset 中優先權最低的元素並輸出。新增工作時，將其優先權插入 multiset。如果收到指令但 multiset 為空，則不執行任何操作。

複雜度分析

• 時間複雜度: O(n log n)
  • 插入和刪除 multiset 中的元素需要 O(log n) 的時間，其中 n 是 multiset 中元素的數量。
  • 題目中最多有 500,000 個輸入，因此最壞情況下時間複雜度為 O(n log n)。
• 空間複雜度: O(n)
  • multiset 儲存所有等待列印的工作優先權，因此空間複雜度為 O(n)。

程式碼

#include <iostream>
#include <set>
using namespace std;
multiset <int> s;
int n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		if(n==0)break;
		if(n==-1){
			if(s.empty()==0){
				cout << *s.begin() << " ";
				s.erase(s.begin());
			}
		}
		else if(n==-2){
			if(s.empty()==0){
				cout << *(--s.end()) << " ";
				s.erase(--s.end());
			}
		}
		else{
			s.insert(n);
		}
	}
	return 0;
}