如何用C++实现n个1与m个0的最优均匀混合（以1开头）

问题定义 #

需要生成一个以1开头的序列，包含n个1和m个0，满足：

1. 均匀性：连续0的最小、最大出现次数相差不超过1；连续1的最小、最大出现次数相差也不超过1。
2. 最优混合：优先选择连续0和连续1的最大出现次数均更小的解；若一个解的连续0最大次数更小但连续1更大，视为等效解，可任选其一。

示例 #

• n=2, m=2：1010
• n=2, m=5：1001000 或 1000100
• n=5, m=2：1101101 或 1011011 或 1101011

解决思路 #

要实现最优混合，核心是让连续段的最大长度尽可能小，需按以下规则分配连续段：

1. 连续1的段分配：序列以1开头，每一个0段会将1的段分割一次，因此1的总段数为k1 = m + 1。每个1段的基础长度为base1 = n / k1，剩余remain1 = n % k1个1段需要额外多1个1。
2. 连续0的段分配：每一个1段之间可插入一个0段，因此0的总段数为k0 = n（仅当m > 0时有效）。每个0段的基础长度为base0 = m / k0，剩余remain0 = m % k0个0段需要额外多1个0。

通过交替生成1段和0段（最后一个1段后不跟0段），即可构造出符合要求的序列。

C++实现代码 #

#include <iostream>
#include <string>

using namespace std;

string generateOptimalSequence(int n, int m) {
    if (n == 0) return ""; // 无法生成以1开头的序列，返回空字符串
    string result;

    // 计算1的连续段参数
    int k1 = m + 1;
    int base1 = n / k1;
    int remain1 = n % k1;

    // 计算0的连续段参数（仅当m>0时）
    int base0 = 0, remain0 = 0;
    if (m > 0) {
        int k0 = n;
        base0 = m / k0;
        remain0 = m % k0;
    }

    // 交替构造1段和0段
    for (int i = 0; i < k1; ++i) {
        // 添加当前1段
        int current1Len = base1 + (remain1 > 0 ? 1 : 0);
        result.append(current1Len, '1');
        if (remain1 > 0) remain1--;

        // 非最后一个1段时，添加0段
        if (i < k1 - 1 && m > 0) {
            int current0Len = base0 + (remain0 > 0 ? 1 : 0);
            result.append(current0Len, '0');
            if (remain0 > 0) remain0--;
        }
    }

    return result;
}

// 测试用例
int main() {
    cout << generateOptimalSequence(2, 2) << endl;    // 输出：1010
    cout << generateOptimalSequence(2, 5) << endl;    // 输出：1001000
    cout << generateOptimalSequence(5, 2) << endl;    // 输出：1101101
    cout << generateOptimalSequence(3, 0) << endl;    // 输出：111
    cout << generateOptimalSequence(1, 4) << endl;    // 输出：10000
    return 0;
}

代码说明 #

• 当m=0时，直接输出n个1即可；当n=0时，无法生成以1开头的序列，返回空字符串。
• 对于n=5, m=2的场景：1的段数为3，基础长度1，余数2，因此有2个1段为2个1，1个1段为1个1，结合0段的分配（2个0段各1个0），生成1101101，符合最优要求。
• 对于n=2, m=5的场景：0的段数为2，基础长度2，余数1，因此有1个0段为3个0，1个0段为2个0，结合1段的分配（2个1段各1个1），生成1001000，符合最优要求。

内容的提问来源于stack exchange，提问作者user2052436