贪心，记录左边有没有白球，遇到黑球时如果左边有白球将白球变为黑球，如果遍历到最后黑球数量少于白球数量，反转所有黑球。

def func(s):
    white_count = 0
    res = 0
    for i in s:
        if i == 'B':
            if white_count > 0:
                res += 1
                white_count -= 1
        else:
            white_count += 1

    return res


if __name__ == '__main__':
    s = input()
    print(func(s))

题面描述

现在有$L$个黑球、白球从左到右依次排开，形成一个字符串$S$，其中每个字符为'B'（代表黑球）或'W'（代表白球）。要求重新涂色，使得每一个黑球的左边都没有白球。也就是说，所有黑球必须连续地排在最左边，白球连续地排在右边。你可以对已有的$L$个球重新涂颜色（将'B'涂为'W'或将'W'涂为'B'），请问至少需要涂几个球才能满足要求。

思路

为了满足条件“每一个黑球的左边不能有白球”，我们可以将所有黑球集中在字符串的最左边，所有白球集中在最右边。为了达到这一点，我们需要找到一个分割点，使得分割点左边全部为黑球，右边全部为白球。为了最小化重新涂色的数量，我们可以考虑以下步骤：

1. 遍历所有可能的分割点：包括在字符串的最左边和最右边。
2. 计算每个分割点需要重新涂色的数量：
   • 分割点左边原本为白球的需要涂成黑球。
   • 分割点右边原本为黑球的需要涂成白球。
3. 选择重新涂色数量最少的分割点。

为了高效计算，我们可以预处理每个位置左边的白球数量和右边的黑球数量，利用前缀和和后缀和的方法，可以在O(n)的时间复杂度内完成计算。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    string S;
    cin >> S;
    int n = S.size();
    // prefixW[i]表示前i个字符中'W'的数量
    vector<int> prefixW(n+1, 0);
    for(int i=0;i<n;i++){
        prefixW[i+1] = prefixW[i] + (S[i] == 'W' ? 1 : 0);
    }
    // suffixB[i]表示从i到末尾'B'的数量
    vector<int> suffixB(n+1, 0);
    for(int i=n-1;i>=0;i--){
        suffixB[i] = suffixB[i+1] + (S[i] == 'B' ? 1 : 0);
    }
    // 遍历所有分割点，找到最小的prefixW[i] + suffixB[i]
    int min_changes = INT32_MAX;
    for(int i=0;i<=n;i++){
        min_changes = min(min_changes, prefixW[i] + suffixB[i]);
    }
    cout << min_changes;
}

python

# 读取输入字符串
S = input().strip()
n = len(S)

# prefixW[i]表示前i个字符中'W'的数量
prefixW = [0] * (n + 1)
for i in range(n):
    prefixW[i+1] = prefixW[i] + (1 if S[i] == 'W' else 0)

# suffixB[i]表示从i到末尾'B'的数量
suffixB = [0] * (n + 1)
for i in range(n-1, -1, -1):
    suffixB[i] = suffixB[i+1] + (1 if S[i] == 'B' else 0)

# 遍历所有分割点，找到最小的prefixW[i] + suffixB[i]
min_changes = float('inf')
for i in range(n+1):
    min_changes = min(min_changes, prefixW[i] + suffixB[i])

print(min_changes)

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        int n = S.length();
        // prefixW[i]表示前i个字符中'W'的数量
        int[] prefixW = new int[n+1];
        for(int i=0;i<n;i++){
            prefixW[i+1] = prefixW[i] + (S.charAt(i) == 'W' ? 1 : 0);
        }
        // suffixB[i]表示从i到末尾'B'的数量
        int[] suffixB = new int[n+1];
        for(int i=n-1;i>=0;i--){
            suffixB[i] = suffixB[i+1] + (S.charAt(i) == 'B' ? 1 : 0);
        }
        // 遍历所有分割点，找到最小的prefixW[i] + suffixB[i]
        int min_changes = Integer.MAX_VALUE;
        for(int i=0;i<=n;i++){
            min_changes = Math.min(min_changes, prefixW[i] + suffixB[i]);
        }
        System.out.println(min_changes);
    }
}