POJ 3481 Double Queue
描述:
新成立的BIG-Bank在不切雷斯特開了一間新辦公室,使用了由IBM羅馬尼亞的現代計算機辦公環境,運用了現代信息技術.一般來說,銀行的每個顧客都有一個識別碼K,并且每一個來銀行的顧客都會被給予一個優先級P.銀行主管的一個大膽想法震驚了公司的軟件工程師.他希望有時候能打破傳統,讓服務窗口給優先級最低的顧客而不是優先級最高的服務.因此,管理系統會收到以下幾種請求.
?
0 | 系統停止運行 |
1 K P | 將編號為K的顧客以P的優先級加入等待名單 |
2 | 為優先級最高的顧客服務并且將其從等待名單中移除 |
3 | 為優先級最低的顧客服務并且將其從等待名單中移除 |
?
你的任務是幫助軟件工程師來編寫這個顧客管理系統.
?
輸入:
輸入的每一行有一個請求;只有最后一行會要求停止運行(請求0).你需要保證當添加一個新顧客到名單中(請求1)時,名單中沒有編碼相同或優先級相同的顧客..
?
輸出:
對于請求2和請求3,程序需要在不同行標準輸出客戶編號K,如果此時名單為空,那么輸出0.
?
Sample Input
2 1 20 14 1 30 3 2 1 10 99 3 2 2 0
Sample Output
0 20 30 10 0
這道題很顯然是平衡樹問題,對于平衡數,C++的STL庫其實有一個自帶的封裝紅黑樹,就是set,這道題如果用STL庫的set就非常簡單了。
注意幾點,這道題需要記錄客戶數據,所以可以新開一個數組來記錄(因為set中的元素就是鍵值也就是優先級,所以要單獨記錄顧客編號)。
這里面用到的主要是set里的insert,end,begin和erase操作,簡單講一下
insert(p)向容器中插入元素p
begin()返回第一個元素的迭代器地址
end()返回最后一個元素的迭代器地址
erase(p)從容器中刪除元素p,這里要注意,set中元素的值是唯一的。
#include<set> #include<iostream> #define MAXN 10000010 using namespace std; int a[MAXN],c[1000010],k,p,op; set<int>li(a,a+MAXN); set<int>::iterator it; int main(){li.clear();while(op=(getchar()-'0')){if(op==1){scanf("%d %d",&k,&p);c[p]=k;li.insert(p);}if(op==2){if(li.empty()){printf("0\n");continue;}it=li.end();it--;printf("%d\n",c[*it]);li.erase(*it);}if(op==3){if(li.empty()){printf("0\n");continue;}it=li.begin();printf("%d\n",c[*it]);li.erase(*it);}} }
?