每日一题 - 240117 - B. Bus of Characters

• B. Bus of Characters

• TAG - $算法?【STL?优先队列、重载运算符】$
• 时间复杂度 - $O(N?\log N)$

//
#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int N = 2e5 + 6;
struct A {
    int idx, w;
} in[N];

struct cmp0 {
    bool operator()(const A& x, const A& y) const { return y.w < x.w; }
};

struct cmp1 {
    bool operator()(const A& x, const A& y) const { return y.w > x.w; }
};

void solve() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int ai;
        scanf("%d", &ai);
        in[i] = (A){i, ai};
    }

    priority_queue<A, vector<A>, cmp0> q0;
    priority_queue<A, vector<A>, cmp1> q1;

    for (int i = 1; i <= n; i++) q0.push(in[i]);

    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') {
            A tt = q0.top(); q0.pop();

            printf("%d%c", tt.idx, " \n"[i == s.size() - 1]);
            q1.push(tt);
        } else if (s[i] == '1') {
            A tt = q1.top(); q1.pop();

            printf("%d%c", tt.idx, " \n"[i == s.size() - 1]);
        }
    }
}

signed main() {
    int t = 1;
    // scanf("%d", &t);
    while (t--) solve();

    return 0;
}

实现细节

• `

参考示意图

• `

参考链接

• c++优先队列priority_queue（自定义比较函数）
• priority_queue 优先队列_自定义比较函数_four_means
• //
• 优先队列的时间复杂度

作者 | 乐意奥AI