top1编程
← 返回题目
题解

【基础】奖牌整理

1 条题解

  • 0
    @ 2026-7-29 0:15:44
    #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