三个vector实现,时间复杂度O(max(M,N))
公司食堂
http://www.nowcoder.com/questionTerminal/601815bea5544f389bcd20fb5ebca6a8
一开始用的两个堆,做的时候11的用例一直超时,改成一个,还是超时,最后用三个数组实现,还是超时,破防提交后发现是cin,cout问题。发现题解基本都用堆,提供一个用数组的思路,三个数组p1,p2,p3,p1存储0人桌子,p2储存一开始的1人桌,p3储存由0人桌变成1人桌的1人桌,用三个指针记录三种桌子的首个可以做位置,对于女生,优先考虑0人桌,其次是p2,p3中最靠前的,坐下后该位置指针++,如果坐的是0人桌在p3中插入该位置,男生优先考虑p2,p3,其次p1,具体操作同理
using namespace std;
int main(){
int groups = 0;
cin >> groups;
while(groups > 0){
groups--;
int n;
cin >> n;
vector<int>p1;
vector<int>p2;
char str[n+1];
scanf("%s",str);
for(int i = 1;i <= n;i++){
char c= str[i-1];
if(c == '0'){
p1.push_back(i);
}
else if(c == '1'){
p2.push_back(i);
}
}
int j = 0;
int k = 0;
int z = 0;
vector<int> p3;
int m;
cin >> m;
char str1[m+1];
scanf("%s",str1);
for(int i = 0;i < m;i++){
char c= str1[i];
if(c == 'M'){
if(k < p2.size()){
if(z < p3.size() && p3[z] > p2[k]){
int cur = p2[k];
k++;
cout << cur << '\n';
}
else if(z < p3.size() && p3[z] < p2[k]){
int cur = p3[z];
z++;
cout << cur << '\n';
}
else{
int cur = p2[k];
k++;
cout << cur << '\n';
}
}
else if(z < p3.size()){
if( k < p2.size() && p3[z] > p2[k]){
int cur = p2[k];
k++;
cout << cur << '\n';
}
else if( k < p2.size() &&p3[z] < p2[k]){
int cur = p3[z];
z++;
cout << cur << '\n';
}
else{
int cur = p3[z];
z++;
cout << cur << '\n';
}
}
else {
int cur = p1[j];
j++;
cout << cur << '\n';
p3.push_back(cur);
}
}
else{
if( j < p1.size()){
int cur = p1[j];
j++;
cout << cur << '\n';
p3.push_back(cur);
}
else{
if(k >= p2.size()){
int cur = p3[z];
z++;
cout << cur << '\n';
continue;
}
if(z < p3.size() && p3[z] > p2[k]){
int cur = p2[k];
k++;
cout << cur << '\n';
}
else if(z < p3.size() && p3[z] < p2[k]){
int cur = p3[z];
z++;
cout << cur << '\n';
}
else{
int cur = p2[k];
k++;
cout << cur << '\n';
}
}
}
}
}
}