Moe's CF Life

Problem: 1659A - Red Versus Blue

嘿嘿，主人！这道题可好玩啦~ 想象一下，有两支队伍，红队 (Red) 和蓝队 (Blue)，他们打了 n 场比赛。红队赢了 r 场，蓝队赢了 b 场，而且我们知道红队更厉害一些，所以 r > b。

虽然我们错过了直播，但我们想脑补一个最最精彩的比赛过程！所谓“精彩”，就是指两队比分咬得很紧，没有任何一队出现“超长连胜”的情况。我们的任务就是，构造一个长度为 n 的字符串（由 'R' 和 'B' 组成），代表比赛结果，使得其中连续相同字符（即连胜）的最大长度尽可能小。

举个栗子喵：比如 RBRBRBR，这里面最长的连胜是 1（单个 'R' 或 'B'），这就非常“焦灼”啦。而 RRRBRR 里面，最长连胜就是 3（开头的 'RRR'）。

我们要做的，就是找出那个让最大连胜长度最小的比赛记录字符串。如果有多种答案，随便输出一种就可以啦，喵~

解题思路 (ฅ'ω'ฅ)

主人请看，这道题的关键在于“最小化最大连胜”。因为题目告诉我们红队赢的次数 r 总是比蓝队 b 多 (r > b)，所以最长的连胜队伍，毫无疑问会是红队 'R' 啦。所以我们的目标就变成了：如何打散这些 'R'，让连续的 'R' 尽可能短？

最好的打散工具是什么呢？当然是我们的蓝队 'B' 啦！我们可以把 b 个 'B' 看作是“隔板”，用来把一大长串的 'R' 分割成一小段一小段的。

想象一下，我们有 b 个 'B'。把它们像这样排开：

_ B _ B _ B _ ... _ B _

看到了吗？b 个 'B' 可以创造出 b + 1 个可以放置 'R' 的空位（或者叫“小区块”）！

为了让每个小区块里的 'R' 数量尽可能平均（从而让最长的那个区块也尽可能短），我们就要采用“平均分配”的策略。这就像给 b+1 只小猫分 r 条小鱼干一样！

先算一下每个区块至少能分到多少个 'R'：这就是一个简单的整除运算 r / (b + 1)。我们叫它 base_run_length 吧。
剩下的 'R' 怎么办呢？分完之后，可能还剩下一些 'R'，数量是 r % (b + 1)。这些多出来的 'R'，我们就一个一个地分给前面的区块，每个区块分一个，直到分完为止。

这样一来，有些区块会有 base_run_length + 1 个 'R'，剩下的区块会有 base_run_length 个 'R'。这样分配是最均匀的，所以最长的一段 'R' 的长度就是 base_run_length + 1 (如果余数不为0) 或者 base_run_length (如果余数是0)，这已经是我们能做到的最小极限啦！

所以，我们的构建步骤就是：循环 b + 1 次，每次构建一个区块。在每个区块里，先放 base_run_length 个 'R'。如果还有多余的 'R' 需要分配，就在这个区块里再多放一个 'R'。除了最后一个区块外，每个区块后面都跟上一个 'B' 作为分隔符。

搞定啦，是不是很简单喵~ ( ´ ▽ ` )ﾉ

代码题解

下面就是把我们刚才的想法变成代码啦，主人请看~

cpp

#include <iostream>

// 这个函数是解决单个测试用例的核心逻辑喵~
void solve() {
    int n, r, b;
    std::cin >> n >> r >> b;

    // 核心思想就是用 'b' 个蓝队胜利 'B' 作为隔板，
    // 去分割 'r' 个红队胜利 'R'。
    // 这样就创造出了 b+1 个小区块，可以用来放 'R'。
    int num_segments = b + 1;

    // 为了让 'R' 的最大连胜长度最小，我们要把 'r' 个 'R' 尽可能均匀地
    // 分配到这 b+1 个区块里。
    // 根据除法原理，每个区块至少能分到 r / (b+1) 个 'R'。
    // 这就是每个 'R' 连胜串的基础长度啦。
    int base_run_length = r / num_segments;

    // r % (b+1) 是余数，它告诉我们有多少个区块能幸运地多得到一个 'R'。
    int extra_r_count = r % num_segments;

    // 我们开始遍历这 b+1 个区块来构建字符串。
    for (int i = 0; i < num_segments; ++i) {
        // 先为当前区块打印基础数量的 'R'。
        for (int j = 0; j < base_run_length; ++j) {
            std::cout << 'R';
        }

        // 如果还有多余的 'R' 没分配完，就给当前这个区块多加一个 'R'，
        // 然后把待分配的额外 'R' 数量减一。
        if (extra_r_count > 0) {
            std::cout << 'R';
            extra_r_count--;
        }

        // 在每个 'R' 区块后面，我们都放一个 'B' 作为隔板。
        // 总共有 'b' 个 'B' 要放，所以最后一个 'R' 区块后面就不用放啦。
        if (i < b) {
            std::cout << 'B';
        }
    }
    std::cout << '\n'; // 一个测试用例结束，换行！
}

int main() {
    // 这两行是加速输入输出的魔法哦，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 读取有几组测试数据
    while (t--) {
        solve(); // 循环解决每一组
    }

    return 0; // 完美结束，喵~
}

Problem: 1659A - Red Versus Blue

解题思路 (ฅ'ω'ฅ)

代码题解

相关知识点介绍

1. 贪心算法 (Greedy Algorithm)

2. 抽屉原理 (Pigeonhole Principle)

Problem: 1659A - Red Versus Blue ​

解题思路 (ฅ'ω'ฅ) ​

代码题解 ​

相关知识点介绍 ​

1. 贪心算法 (Greedy Algorithm) ​

2. 抽屉原理 (Pigeonhole Principle) ​

Problem: 1659A - Red Versus Blue

解题思路 (ฅ'ω'ฅ)

代码题解

相关知识点介绍

1. 贪心算法 (Greedy Algorithm)

2. 抽屉原理 (Pigeonhole Principle)