C++ 算法：最大化金牌连续段长度

在不同的比赛中你得到了 n 枚奖牌，每枚奖牌为金牌或银牌。这些奖牌现在按顺序排成一排。你可以交换任意一对奖牌的位置（不一定是相邻的），安排一下奖牌的顺序，让尽可能多的金牌连续排在一起，即最大化最长金牌连续长度。最多允许做一次交换，求金牌最长连续段。

代码示例

#include <iostream>
#include <vector>

using namespace std;

int maxConsecutiveGold(vector<char>& medals) {
    int n = medals.size();
    int maxLen = 0;
    int goldCount = 0;
    int maxGoldCount = 0;

    // 计算初始金牌数量和最大金牌数量
    for (int i = 0; i < n; i++) {
        if (medals[i] == 'G') {
            goldCount++;
            maxGoldCount++;
        }
    }

    // 统计每个位置交换后的最大金牌连续长度
    for (int i = 0; i < n; i++) {
        // 如果当前位置是金牌，则金牌数量减一
        if (medals[i] == 'G') {
            goldCount--;
        }
        // 如果当前位置是银牌，则金牌数量加一
        else {
            goldCount++;
        }

        // 更新最大金牌连续长度
        maxLen = max(maxLen, goldCount);

        // 统计每个位置交换后的最大金牌数量
        maxGoldCount = max(maxGoldCount, goldCount);
    }

    // 如果最大金牌数量等于金牌总数，说明已经是最优解，无需交换
    if (maxGoldCount == goldCount) {
        return maxLen;
    }

    // 否则，需要交换一次来达到最优解
    maxLen = max(maxLen, maxGoldCount + 1);

    return maxLen;
}

int main() {
    int n;
    cin >> n;

    vector<char> medals(n);
    for (int i = 0; i < n; i++) {
        cin >> medals[i];
    }

    int maxConsecutive = maxConsecutiveGold(medals);
    cout << maxConsecutive << endl;

    return 0;
}

通过输入n和奖牌序列，程序会输出金牌的最长连续段长度。注意，这里假设输入的奖牌序列只包含'G'和'S'两种字符，且n为正整数。

算法解释

首先，计算初始金牌数量和最大金牌数量，它们表示没有进行任何交换时的初始情况。
然后，遍历每个奖牌位置，模拟交换操作，即假定当前位置的奖牌被交换，并计算交换后的金牌数量和最大金牌连续长度。
比较每次交换后的最大金牌连续长度，并更新最大值。
最后，如果最大金牌数量等于金牌总数，则无需交换，直接返回最大金牌连续长度。否则，需要进行一次交换，此时最大金牌连续长度为最大金牌数量加 1。

示例

假设输入的奖牌序列为 'GGSSGGS'，则程序的输出为 4。这是因为我们可以交换第一个 'S' 和最后一个 'G'，得到 'GGSGSGG'，最大金牌连续段长度为 4。

希望这篇文章能帮助您理解并解决此问题。