Bus of Characters(贪心、模拟栈+队列)

  • Post author:
  • Post category:其他


在角色巴士中有n排座位,每排都有2个座位。 第i排的两个座位的宽度均为w i厘米。 没有相同宽度的座椅。

公共汽车最初是空的。 每个2n站都会有一位乘客进入巴士。 有两种类型的乘客:

一个内向者总是选择两个座位都没人的一排。 在这些排中,他选择座位宽度最小的,并占据了其中的一个座位;

一个外向型的人总是选择有人的一排。 在这些排中,他选择了座位宽度最大的那个,并占据了空位。

你会得到每排座位的宽度和乘客进入公共汽车的顺序。 确定每位乘客将乘坐哪一排。

Input

第一行包含一个整数n(1 ≤ n ≤ 200000) – 总排数。

第二行包含整数w 1,w 2,…,w n(1 ≤ w i ≤ 10 9)的序列,其中wi是第i行中每个座位的宽度。 保证所有 w i 都不同。

第三行包含一个长度为 2n 的字符串,由数字“0”和“1”组成 – 描述乘客进入公共汽车的顺序。 如果第j个字符是 ‘0’,那么在第 j 个车站进入公共汽车的乘客是内向的。 如果第j个字符是 ‘1’,则在第j个车站进入公交车的乘客是外向型的。 保证外向者的数量等于内向者的数量(即两个数字等于 n),并且对于每个外向者总是有合适的行。

Output

打印 2n 个整数 – 乘客将坐的排。 乘客的顺序应与输入的顺序相同。

Sample Input

Input

2

3 1

0011

Output

2 1 1 2

Input

6

10 8 9 11 13 5

010010011101

Output

6 6 2 3 3 1 4 4 1 2 5 5

Hint

在第一个例子中,第一个乘客(内向)选择第二排,因为它具有最小宽度的座位。 第二位乘客(内向)选择第1行,因为它现在是唯一的空行。 第三位乘客(外向型)选择第一排,因为它只有一个占用的座位,座位宽度是这些排中最大的。 第四位乘客(外向性)选择第二排,因为它是唯一一个有空位的排。

/*
贪心算法
用到了 栈(先进后出)、队列(先进先出)、结构体(表示每一排的信息)、排序
按照宽度从小到大排序,遇见0就是存入队列(先进先出),
然后再把这个座位的排号存入 栈(先进后出),
遇见 1 就出栈,将队首元素存入队列,最后利用队列先进先出的性质输出队列
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<stack>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct NODE
{
    long long int m;
    long long int w;
}node[200001];
stack<long long int>s;
queue<long long int>q;
bool cmp(struct NODE a,struct NODE b)
{
    return a.w<b.w;
}
int main()
{
    long long int n,i,j;
    string a;
 // 定义字符串 
    scanf("%lld",&n);
    for(i=0;i<n;i++){
        scanf("%lld",&node[i].w);
        node[i].m=i+1;
    }
    sort(node,node+n,cmp);
    cin>>a;
    int flag=0;
    for(i=0;i<a.size();i++){
        if(a[i]=='0'){
            q.push(node[flag].m);
            s.push(node[flag++].m);
        }
        else{
            int data=s.top();
            s.pop();
            q.push(data);
        }
    }
    while(!q.empty()){
        cout<<q.front()<<" ";
        q.pop();
    }
    cout<<endl;
}



版权声明:本文为JKdd123456原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。