TAG- 算法 − 【 S T L − 优先队列、重载运算符】 算法 - 【STL - 优先队列、重载运算符】 算法−【STL−优先队列、重载运算符】时间复杂度- O ( N ∗ log N ) O(N \ast \log N) O(N∗logN)
//
#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;
}
实现细节
- `
参考示意图
-
`
参考链接
作者 | 乐意奥AI
