样例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了。。）
