美团笔试题——公司食堂
原理:小根堆,利用优先队列实现。设置seat0和seat1两个优先队列,存放位置为0和1的餐桌号,因小根堆特性,队首为最小值,即较左端餐桌位置。
本题卡endl,改为'\n'换行符输出即AC。endl会刷新输出流缓冲区,多行输出会导致刷新缓冲区过于频繁,导致超时问题。
#include<bits/stdc++.h> #include<list> using namespace std; int main() { int T,N; cin>>T; while(T--) { cin>>N; string str_seat; cin>>str_seat; priority_queue<int,vector<int>,greater<int>> seat0; priority_queue<int,vector<int>,greater<int>> seat1; for(int i = 0; i < N; i++) { if('0' == str_seat[i]) { seat0.push(i+1); } else if('1' == str_seat[i]) { seat1.push(i+1); } } int m; cin>>m; cin>>str_seat; for(int i = 0; i < m; i++) { if(str_seat[i] == 'M') { if(!seat1.empty()){ int f = seat1.top(); cout<<f; seat1.pop(); } else if(!seat0.empty()){ int f = seat0.top(); cout<<f; seat0.pop(); seat1.push(f); } } else if(str_seat[i] == 'F') { if(!seat0.empty()){ int f = seat0.top(); cout<<f; seat0.pop(); seat1.push(f); } else if(!seat1.empty()){ int f = seat1.top(); cout<<f; seat1.pop(); } } } } return 0; }