雲端列印服務公司提出一個新型服務。該公司有 N 台 3D 印表機，其中印表機 P1、P2、…、Pk 用以優先服務最為重要客戶，印表機 Pk+1、Pk+2、…、PN 列印速度較，用以優先服務一般客戶。
每個客戶依該年度所選擇服務等級及所繳交費用可有不同的列印優先權，以 1～10000 表示之；10000 代表最高列印優先權，1 代表最低列印優先權。
為了不讓低列印優先權的客戶永無止盡的等待，印表機 P1～Pk 一旦有空，等待的工作中優先權最高的工作就會被交付列印；而印表機 Pk+1～PN 一旦有空，等待的工作中優先權最低的工作就會被交付列印。
請寫一個程式列舉交付列印工作的順序。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入只有一行，共有不定數量的整數，整數可為「-2, -1, 0, 1, 2, …, 10000」，兩整數之間以一個空白隔開。 -2 表示印表機 P1～Pk 其中一台有空，可以列印最高優先權的工作。 -1 表示印表機 Pk+1～PN 其中一台有空，可以列印最低優先權的工作。 1～10000 代表新增一個優先權為該數字之工作。 0 則代表輸入結束。 若輸入為 -1 或 -2 但無等待列印的工作，則不列印，需等待下一個 -1 或 -2 才再列印新的工作。 | 請依被列印工作的順序，輸出該工作的優先權代號，之後緊接著一個空白。 尚未交付列印的工作不需輸出。 |
| 20 15 10 -2 -1 -1 0 | 20 10 15 |
| 1 2 3 -2 4 5 6 -1 7 0 | 3 1 |
解題思路
使用 deque 來存儲資料，但是會存到同樣的數字，所以要再開一個陣列來紀錄每一種數字出現的次數。因為在 deque 中刪除資料也會耗費時間，所以要盡可能減少刪除資料的次數。
當陣列中紀錄收到的數字並沒有在 deque 中，就要將該數字存到 deque 中，這邊要使用二分插入法來尋找合適的地方做插入，這樣就可以節省排序的時間。如果收到的數字已經存在於 deque 中，則將這個數字的陣列值 +1。
當需要刪除 deque 中的資料時，先確認要刪掉的數字在陣列中的值是否為 1，如果是的話就代表需要在 deque 中刪掉，如果是要刪掉第一個資料就是 pop_front()，最後一個資料就是 pop_back()。如果陣列值不是 1 就代表不需要刪資料，只需要將陣列值 -1 即可。
範例程式碼－ZeroJudge C421: 雲端列印
#include <iostream>
#include <deque>
using namespace std;
deque<int> vv;
int priority[50000] = {};
void bbinsert(const int target) {
int left = 0, right = vv.size();
while(left < right) {
const int middle = (left + right)/2;
if (vv[middle] < target) {
left = middle+1;
}
else {
right = middle;
}
}
vv.emplace(vv.begin()+left, target);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, low = 0, high = 0, demand = 0;
for (int i = 0; i<=10000; i++) priority[i] = 0;
while (cin >> N && N != 0) {
if (N == -1) {
low++;
if (demand > 0) {
const int tmp = vv[0];
cout << tmp << " ";
if (priority[tmp] == 1) {
vv.pop_front();
}
priority[tmp]--;
low--;
demand--;
}
}
else if (N == -2) {
high++;
if (demand > 0) {
const int tmp = vv[vv.size()-1];
cout << tmp << " ";
if (priority[tmp] == 1) vv.pop_back();
priority[tmp]--;
high--;
demand--;
}
}
else {
if (priority[N] == 0) bbinsert(N);
priority[N]++;
demand++;
}
}
cout << "\n";
}
//ZeroJudge C421
//Dr. SeanXD