士兵排列题解

共计 1248 个字符，预计需要花费 4 分钟才能阅读完成。

题面

假如你是长官，现在有一些新兵入伍。但是他们不是同时到达军营集合。对于某一个士兵 i（编号从 1 到 n）, 如果 s[i]=1，那么他从队尾入队，如果 s[i]=0，那么他从队头入队。当所有士兵入队后，这个时候士兵就有一个排列。然后，从队头到队尾，每个士兵会说出他的能力值 a[i]，你需要按照能力值从高到低输出对应的一个排列。

输入描述

对于每组测试样例，

第一行输入一个正整数 n（1≤n≤10^5），表示士兵的个数。

第二行输入一个字符串 s（1≤∣s∣≤10⁵），表示士兵入队的方式。

第三行输入 n 个正整数 ai（1≤ai≤10^ 9^），表示入完队后每个士兵从头到尾说出他自己的能力值。保证每个能力值不同，即 ai != aj(i!=j,1≤i,j≤n)。

输出描述

对于每组测试样例，输出一行排列，表示按上述要求排好序后的一个排列。

样例输入

6
011010
6 1 2 4 5 3

样例输出

6 3 2 5 1 4

 题解

对于这题，我选择使用双向链表，方便插入和遍历。

代码如下，定义链表结构体和排序函数，输入 n、s，创建头指针，遍历字符串创建链表，然后读取用户输入能力并丢进向量，然后把向量排个序输出 id 就解决了。

有一个需要注意的，程序结束后内存自动释放，所以不需要手动释放，但是你如果手动释放了（删除链表），会导致 Segmentation fault，推测是 vector 里还保存着引用的关系？

#pragma GCC optimize(3, "Ofast", "inline")
#include 
#include 
#include 
#include 
using namespace std;

struct Node{
    int id;
    int ability;
    Node* prev;
    Node* next;
    Node(int _id, int _ability, Node* _prev, Node* _next) : id(_id), ability(_ability), prev(_prev), next(_next) {}};

bool cmp(Node *a, Node *b){return a->ability > b->ability;
}

int main(){ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    Node *head = new Node(1, 0, nullptr, nullptr);
    Node *tail = head;
    for(int i=1;iprev = new Node(i+1, 0, nullptr, head);
                head = head->prev;
                break;
            case '1':
                tail->next = new Node(i+1, 0, tail, nullptr);
                tail = tail->next;
        }
    }
    Node *p = head;
    vector v;
    while(p!=nullptr){cin>> p->ability;
        v.push_back(p);
        p = p->next;
    }
    sort(v.begin(), v.end(), cmp);
    for(Node *ptr : v){cout << ptr->id <<" ";}
    return 0;
}