题解
【基础】奖牌整理
1 条题解
-
0
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { int n; string s; cin >> n >> s; // 1. 统计G/S/B的总数 int g_cnt = count(s.begin(), s.end(), 'G'); int s_cnt = count(s.begin(), s.end(), 'S'); int b_cnt = n - g_cnt - s_cnt; // 2. 划分区域:G区[0, g_cnt), S区[g_cnt, g_cnt+s_cnt), B区[g_cnt+s_cnt, n) int g_in_s = 0, g_in_b = 0; // G区中出现的S/B数量 int s_in_g = 0, s_in_b = 0; // S区中出现的G/B数量 int b_in_g = 0, b_in_s = 0; // B区中出现的G/S数量 // 遍历G区(应全为G) for (int i = 0; i < g_cnt; ++i) { if (s[i] == 'S') g_in_s++; else if (s[i] == 'B') g_in_b++; } // 遍历S区(应全为S) for (int i = g_cnt; i < g_cnt + s_cnt; ++i) { if (s[i] == 'G') s_in_g++; else if (s[i] == 'B') s_in_b++; } // 遍历B区(应全为B) for (int i = g_cnt + s_cnt; i < n; ++i) { if (s[i] == 'G') b_in_g++; else if (s[i] == 'S') b_in_s++; } // 3. 计算最少交换次数 int res = 0; // 第一步:交换G区的S和S区的G(一次修复2个错误) int swap1 = min(g_in_s, s_in_g); res += swap1; g_in_s -= swap1; s_in_g -= swap1; // 第二步:交换G区的B和B区的G(一次修复2个错误) int swap2 = min(g_in_b, b_in_g); res += swap2; g_in_b -= swap2; b_in_g -= swap2; // 第三步:交换S区的B和B区的S(一次修复2个错误) int swap3 = min(s_in_b, b_in_s); res += swap3; s_in_b -= swap3; b_in_s -= swap3; // 第四步:剩余错误为三方循环(G→S→B→G),每3个错误需要2次交换 // 剩余错误数:g_in_s + g_in_b = s_in_g + s_in_b = b_in_g + b_in_s int remain = g_in_s + g_in_b; res += remain * 2; cout << res << endl; return 0; }
- 1