题面描述

现在有$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);
    }
}

题目内容

现在有$L$个黑球、白球从左到右依次排开，现在要求每一个黑球的左边不能有白球，为此可以对已有的L个球重新涂颜色(白涂黑或黑涂白)，至少需要涂几个球才能满足要求。

输入描述

输入只有一行，包含一个字符串$S$，且只包含'$B$'(代表黑球)或者'$W$'(代表白球)。

我们保证字符串$S$的长度$L$的范围是($0<L<10000$)。

输出描述

需要被重新涂颜色的球最少数量。

样例1

输入

BWBWB		

输出

2

样例2

输入

BBBWWW

输出

0