Bus of Characters

题目描述

在一辆公交车中有n排座位，每一排有两个座位。第i排的两个座位的宽度均为 wi。所有的wi互不相同。

初始时，公交车是空的。接下来会依次停靠2n个站，每一站将上来一名乘客。 乘客分为两类：

内向者：此类乘客总是会选择两个座位都是空的那一排就坐，如果有多排都是空的，他将会选择wi最小的那一排中任意一个空座坐下。

外向者：此类乘客总是会选择已有一人就坐（当然是内向者）的那一排，如果有多排都满足条件，他会选择 wi最大的那一排的空座坐下。

现在给定每一排的宽度 wi以及乘客上车的顺序。请确定每一个乘客将会选择哪一排坐下。

输入格式

第一行包括一个整数n (1<=n<=200000)——公交车中座位的排数。

第二行为一个序列 w1,w2,…,wn(1<=wi<=10^9)，其中wi为第i排的座位的宽度。保证所有的wi互不相同。

第三行是一个长度为2n 的01字符串，表示乘客上车的顺序。如果第j个字符为'0'，表示第 j 名乘客是内向者，如果第 j 个字符为'1'，表示第j名乘客是外向者。数据保证内向者和外向者人数相同（即均为 n），对每一名上车的外向者，保证有空座位可以坐。

输出格式

输出2n 个整数，空格分开，表示每名乘客会选哪一排就座。

数据范围与提示

样例解释：

第1名乘客（内向者）选择了第2排（由于它的宽度最小）。

第2名乘客（内向者）选择了第1排（由于它是唯一的没有人坐的那排）。

第3名乘客（外向者）选择了第1排（由于它正好是有一个人落座，并且宽度最大）。

第4名乘客（外向者）选择了第2排（由于它是唯一的有空座的那排）。

输入输出样例

样例1

输入样例 复制

2

3 1

0011

输出样例 复制

2 1 1 2

#include <bits/stdc++.h>
using namespace std;
int w[200010],vis[200010];
string p;
int person[400010];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
    	cin>>w[i];
	}
	cin>>p;
	int t=0;
	for(int i=p.size()-1;i>=0;i--) {
		person[++t]=p[i]-'0';
	}
	for(int i=p.size();i>0;i--) {
		if(person[t]) {
			int s=0;
			for(int j=1;j<=n;j++) {
				if(vis[j]==1&&(w[j]>w[s]||s==0)) s=j;
			}
			vis[s]++;
			t--;
			cout<<s<<" ";
		}
		else {
			int s=0;
			for(int j=1;j<=n;j++) {
				if(vis[j]==0&(w[j]<w[s]||s==0))s=j;
			}
			vis[s]++;
			t--;
			cout<<s<<" ";
		}
	}
    return 0;
}