前言:

前陣子在zerojudge上轉轉，想說寫一下之前全國賽的題目，恰好看見這一題，還是當年(104)的pA(水題)，研究了一小下很快就解開了

題目敘述:

雲端列印服務公司提出一個新型服務。
該公司有 n 台 3D 印表機,其中印表機 P1,P2, …, Pk 用以優先服務最為重要客戶,印表機 Pk+1, Pk+2, …, Pn 列印速度較慢,用以優先服務一般客戶。
每個客戶依該年度所選擇服務等級及所繳交費用可有不同的列印優先權, 以 1, …, 10000 表示之;10000 代表最高列印優先權,1 代表最低列印優先權。
為了不讓低列印優先權的客戶永無止盡的等待,印表機 P1, P2, …, Pk 一旦有空,等待的工作中優先權最高的工作就會被交付列印;
而印表機 Pk+1, Pk+2, …, Pn一旦有空, 等待的工作中優先權最低的工作就會被交付列印。
請寫一個程式列舉交付列印工作的順序。
-2 表示印表機 P1, P2, …, Pk其中一台有空, 可以列印最高優先權的工作;-1 表示印表機 Pk+1, Pk+2, …, Pn其中一台有空, 可以列印最低優先權的工作;1, 2, …, 10000

想法:

簡單講，就是一個數列，當中出現-1的話就輸出當前數列中數值最小的值，出現-2就輸出當前最小的值。請注意，這邊的當前是指在”-1”以及”-2”之前且不包含”-1”、”-2”，如果出現0就代表數列結束。

這一題並不算太複雜，僅僅需要了解一些程式技巧以及STL的使用就可以了。我們來分析一下題目:
有一個陣列結尾的數值，所以這一題顯然是要使用重複輸入的技巧，如果有”-1”、”-2”要輸出當前的極值，而且數列可能非常的長，如果一直sort肯定會吃TLE，所以我們需要一個可以幾乎是O(1)插入並且自動排序的資料結構，那就非set莫屬了。又因為可能出現重複的數字，所以要使用multiset，其使用方式與set雷同，唯一差異處就是可允許重複單元存在。

以下為題解:

題解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;

multiset<int> s;

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int x,cnt=0;

    while(cin >>x){
        if(x==0)break;
        if(x==-1 && cnt){
            cout<<*s.begin()<<" ";
            s.erase(s.begin());
            cnt--;  
        }else if(x==-2 && cnt){
            auto it=s.end();
            it--;
            cout<<*it<<" ";
            s.erase(it);
            cnt--;
        }else if(x>0)s.insert(x),++cnt;
        
    }
    cout<<'\n';

}