P4649 红绿蓝（基础）

解题思路

罐子里有红色 R、绿色 G、蓝色 B 三种玻璃珠，要求先把它们排成一行，按英文字母的顺序 B、G、R 排列，再计算能串成多少串幸运珠。每串幸运珠需要 3 颗蓝色、2 颗绿色、1 颗红色。

**第一步，读懂题意。**有两个问题要回答：一是把玻璃珠按 B、G、R 的顺序排好输出；二是算最多能串成多少串幸运珠。

**第二步，解决第一问：排序。**只要分别数出蓝色、绿色、红色各有几颗，然后先输出全部 B，再输出全部 G，最后输出全部 R，就是排好序的字符串。比如样例 RRGRRGGBBGB 中，B 有 3 颗、G 有 4 颗、R 有 4 颗，所以第一行输出 BBBGGGGRRRR。因为字母 B 排在 G 前面、G 排在 R 前面，把同色珠子集中在一起输出，就天然符合英文字母顺序。

**第三步，解决第二问：木桶原理。**每串需要 3 蓝 2 绿 1 红，所以能串的串数由三种珠子共同决定，取它们各自能支持的串数的最小值。蓝色 3 颗支持 3÷3=1 串，绿色 4 颗支持 4÷2=2 串，红色 4 颗支持 4÷1=4 串，取最小值 1 串，与样例一致。这就是「木桶原理」：最短的那块板决定能装多少水，最缺的那种珠子决定能串多少串。

**第四步，用代码实现。**先扫描一遍字符串统计三种颜色的数量；然后分别输出三种颜色的字符；最后用蓝色数量除以 3、绿色数量除以 2、红色数量除以 1，取三个结果的最小值作为答案。

**第五步，确认边界。**字符串长度最长 10000，用定长字符数组保存；题目保证三种字母都至少出现一次，所以不会出现除以 0 的情况。如果某种颜色很多，多的部分会放回罐子里，不影响结果。

参考代码

// 统计红绿蓝玻璃珠，输出排序结果和幸运珠串数
#include <iostream>
using namespace std;

int main() {
    char beads[10005]; // 保存输入的玻璃珠字符串
    cin >> beads; // 读入玻璃珠排列
    int blueCnt = 0; // 蓝色玻璃珠数量
    int greenCnt = 0; // 绿色玻璃珠数量
    int redCnt = 0; // 红色玻璃珠数量
    int length = 0; // 字符串长度
    while (beads[length] != '\0') { // 从头数到字符串末尾
        if (beads[length] == 'B') { // 当前珠子是蓝色
            blueCnt++; // 蓝色数量加一
        } else if (beads[length] == 'G') { // 当前珠子是绿色
            greenCnt++; // 绿色数量加一
        } else { // 当前珠子是红色
            redCnt++; // 红色数量加一
        }
        length++; // 移到下一个字符
    }
    for (int i = 0; i < blueCnt; i++) { // 先输出全部蓝色珠子
        cout << 'B'; // 输出一个蓝色字符
    }
    for (int i = 0; i < greenCnt; i++) { // 再输出全部绿色珠子
        cout << 'G'; // 输出一个绿色字符
    }
    for (int i = 0; i < redCnt; i++) { // 最后输出全部红色珠子
        cout << 'R'; // 输出一个红色字符
    }
    int groups = blueCnt / 3; // 按蓝色数量最多能组成的组数
    if (greenCnt / 2 < groups) { // 绿色数量限制更少时
        groups = greenCnt / 2; // 用绿色数量更新组数
    }
    if (redCnt < groups) { // 红色数量限制更少时
        groups = redCnt; // 用红色数量更新组数
    }
    cout << '\n' << groups << '\n'; // 输出换行和幸运珠串数
    return 0; // 程序结束
}

复杂度分析

程序只扫描字符串一次统计三种珠子的数量，再分别输出，时间复杂度是 O(len)，len 是字符串长度，最大 10000，非常快。空间上只用了一个字符数组保存输入，空间复杂度是 O(len)。