MT3027 red and blue

本文主要是介绍MT3027 red and blue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

样例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;elsereturn 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; // 默认yesfor (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;elsecout << "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;                  // 默认yesfor (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~nfor (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; // 默认yesfor (auto i : a){if (i.v != t){f = 0;cout << "NO" << endl;break;}else{t++;}}if (f == 1){cout << "YES" << endl;}}
}

（样例倒数第二个输出不对，但也AC了。。）

这篇关于MT3027 red and blue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---