题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$，长为$n$的字符串$s$，仅包含B和R。

每次操作，你可以选择一个下标$i$。
如果$s[i]=$B，把$a[i]$减少$1$。
如果$s[i]=$R，把$a[i]$增加$1$。

能否在执行若干次（或者零次）操作后，把数组$a$变成一个$1$到$n$的排列？
输出YES或NO。

输入样例

8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR

输出样例

YES
NO
YES
YES
NO
YES
YES
YES

算法

贪心

假设B位置的元素有$b$个，R位置的元素有$r$个。比较容易想到的一种构造方案就是，让所有B的元素构成排列的前$b$项，所有R的元素构成排列的后$r$项。因此，将所有B和R位置的元素$a[i]$分别存入到$dec$和$inc$两个数组中并排序，按照顺序来构建$1$到$n$的排列。

在构造的过程中需要满足：$inc$中的元素不能太大，即$inc[i] \gt b+i+1$时不合法（$i$从$0$开始）。$dec$中的元素不能太小，即$dec[i] \lt i+1$时不合法。

复杂度分析

时间复杂度

遍历一遍$s$串构建$inc$和$dec$两个数组，时间复杂度为$O(n)$。对$inc$和$dec$排序，时间复杂度为$O(nlog_2n)$。最后遍历这两个有序数组进行验证，时间复杂度为$O(n)$。综上，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

排序的空间复杂度为$O(log_2n)$（快速排序），但瓶颈在于$inc$和$dec$两个数组，两个数组加起来的空间复杂度为$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 200010;
int T, n, a[N];
char s[N];

bool solve() {
    vector<int> dec, inc;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'B') {
            dec.push_back(a[i]);
        }else {
            inc.push_back(a[i]);
        }
    }
    sort(inc.begin(), inc.end());
    sort(dec.begin(), dec.end());
    for(int i = 0; i < dec.size(); i++) {
        if(dec[i] < i + 1) return false;
    }
    int offset = dec.size();
    for(int i = 0; i < inc.size(); i++) {
        if(inc[i] > offset + i + 1) return false;
    }
    return true;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        scanf("%s", s + 1);
        bool flag = solve();
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}