Blue-Red Permutation

链接

题目链接

题意

给你 n 个数，这几个数有 2 中颜色，红色或者蓝色，你可以对蓝色的数减 1，也可以对红色的数加 1，问你是否可以将这 n 个数变成 1-n 的一个排列

思路

对蓝色的数来说，它只能减 1，因此越小的蓝色数可以变成的数越少，如蓝色的 3 只能变成 1、2、3，而蓝色的 5 可以变成 1、2、3、4、5，因此优先使用蓝色的比较小的数变成 1-n 中比较小的数，而红色的数的操作恰好相反

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <set>
typedef long long ll;
using namespace std;
#define ioClose() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'const int maxn = 2e5 + 5;
const int mod = 998244353;
int a[maxn];
// l 存放蓝色的数，用小顶堆
priority_queue<int, vector<int>, greater<int>> l;
// r 存放红色的数，用大顶堆
priority_queue<int> r;
// b[i] 代表是否已经有其他数变成 i 
bool b[maxn];
int main() {
    ioClose();int t;scanf("%d", &t);while (t--) {
    while (!l.empty()) l.pop();while (!r.empty()) r.pop();memset(b, false, sizeof(b));int n;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);getchar();for (int i = 1; i <= n; i++) {
    char ch = getchar();if (ch == 'B') l.push(a[i]);else r.push(a[i]);}int count = 0;// 优先使用蓝色的比较小的数变成 1-n 中比较小的数for (int i = 1; i <= n; i++) {
    if (l.empty()) break;if (l.top() >= i) {
    l.pop();b[i] = true;count++;}}// 优先使用红色的比较大的数变成 1-n 中比较大的数for (int i = n; i >= 1; i--) {
    if (r.empty()) break;if (r.top() <= i && !b[i]) {
    r.pop();b[i] = true;count++;}}// 如果能变成 1-n 的数目恰好等于 n 则代表可以将这 n 个数变成 1-n 的一个排列puts((count == n) ? "YES" : "NO");}return 0;
}