样例1：
输入：
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有x个，则R有n-x个。让B和R的优势都发挥出来，即让B尽可能变小，变成1~x的数；让R尽可能变大，变成值的范围为x+1~n的数。B往后排，R往前排。
先排B再排R，即先按BBBRRR排列，再按1234排列。
正确代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int t, n;
struct aa
{
int v; // 值
char color; // 颜色 r变大，b变小
} a[N];
bool cmp(aa a, aa b)
{
if (a.color == b.color)
return a.v < b.v;
else
return a.color < b.color;
}
int main()
{
cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].v;
for (int i = 0; i < n; i++)
cin >> a[i].color;
sort(a, a + n, cmp);
int flag = 1; // 默认yes
for (int i = 0; i < n; i++)
{
if (a[i].color == 'B' && a[i].v < i + 1)
{
flag = false;
break;
}
if (a[i].color == 'R' && a[i].v > i + 1)
{
flag = false;
break;
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
ps:下面是一个错误代码，样例都过不去，结果居然AC了。。
（下面代码的贪心策略错了，cmp中不应该先判断值再判断颜色，应该反过来）
（如果输入为1,-2，则排序后先对-2分析，color为R可以增大为1；再对1分析，color为B，只能减小不能增大为2，所以输出了NO，但应该输出YES）
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int t, n;
struct aa
{
int v; // 值
char color; // 颜色 r变大，b变小
bool st = false; // 是否被选中
};
bool cmp(aa a, aa b)
{
if (a.v < b.v)
return true;
else if (a.v == b.v && a.color == 'B' && b.color == 'R')
return true;
return false;
}
vector<aa> a;
int main()
{
cin >> t;
while (t--)
{
a.clear();
cin >> n;
int x[N];
char y[N];
for (int i = 0; i < n; i++)
cin >> x[i];
for (int i = 0; i < n; i++)
cin >> y[i];
for (int i = 0; i < n; i++)
a.push_back({x[i], y[i]});
//>n要减小 <1要增大
sort(a.begin(), a.end(), cmp); // r变大，b变小
int flag = 1; // 默认yes
for (auto i : a)
{
if (i.v < 1)
{
if (i.color == 'B')
{
cout << "NO" << endl;
flag = 0;
break;
}
}
else if (i.v > n)
{
if (i.color == 'R')
{
cout << "NO" << endl;
flag = 0;
break;
}
}
}
if (flag == 0)
{
continue;
}
int j = 1; // 1~n
for (vector<aa>::iterator i = a.begin(); i != a.end(); i++)
{
if ((*i).v == j && (*i).st == false)
{
(*i).st = true;
j++;
}
else if ((*i).v != j && (*i).st == false)
{
if ((*i).v > j && (*i).color == 'B')
{
(*i).v = j;
(*i).st = true;
j++;
}
else if ((*i).v < j && (*i).color == 'R')
{
(*i).v = j;
(*i).st = true;
j++;
}
else if ((*i).v > j && (*i).color != 'R') // 找r
{
for (auto k = i; k < a.end(); k++)
{
if ((*k).v > j && (*k).color == 'R' && (*k).st == false)
{
(*k).v = j;
(*k).st = true;
j++;
swap((*i), (*k));
break;
}
}
}
else if ((*i).v < j && (*i).color != 'B') // 找b
{
for (auto k = i; k < a.end(); k++)
{
if ((*k).v < j && (*k).color == 'B' && (*k).st == false)
{
(*k).v = j;
(*k).st = true;
j++;
swap((*i), (*k));
break;
}
}
}
}
}
int t = 1;
int f = 1; // 默认yes
for (auto i : a)
{
if (i.v != t)
{
f = 0;
cout << "NO" << endl;
break;
}
else
{
t++;
}
}
if (f == 1)
{
cout << "YES" << endl;
}
}
}
（样例倒数第二个输出不对，但也AC了。。）
