题目描述 $\text{(Problem Statement)}$

祭坛供奉从左到右排成一排的 $N$ 个石头。
从左边数第 $i\ (1 \leq i \leq N)$ 个石头的颜色以字母 $c _ i$ 的形式给出：R表示红色 $\text{(Red)}$，W表示白色 $\text{(White)}$。

你每次只能执行以下两种操作

• 选择两个石头（不一定要是相邻的）并将二者交换
• 选择一个石头并改变其颜色（从红色变成白色或者从白色变成红色）

算命者说，一块白色的石头放在一块相邻的红色石头的左边会带来灾难。
至少需要多少次操作，可以到达一个没有这样的白色石头的情况？

约定 $\text{(Constraints)}$

• $2 \leq N \leq 200000$
• $c _ i$ 是 R 或 W

输入 $\text{(Input)}$

输入按以下形式的标准输入给出

N
c1 c2 ... cN

输出 $\text{(Output)}$

输出一个整数表示最少需要的操作不熟

输入样例1 $\text{(Sample Input 1)}$

4
WWRR

输出样例1 $\text{(Sample Output 1)}$

2

输入样例2 $\text{(Sample Input 2)}$

2
RR

输出样例2 $\text{(Sample Output 2)}$

0

输入样例3 $\text{(Sample Input 3)}$

8
WRWWRWRR

输出样例3 $\text{(Sample Output 3)}$

3

算法1

(双指针,遍历,枚举) $O(n)$

• 结论：存在一组最优解，其操作序列中不存在操作$2$
• 证明：反证法，假设不存在一组操作序列中不存在操作$2$的最优解，
  即每一组最优解的操作序列中，都存在操作$2$
  先将每个操作序列按操作的位置从小到大
  那么对于其中一组最优解，找到第一个为 $1$ 的操作
  对于这个操作，有两种可能，分类讨论
  • 将某个石头由白色变为红色
    执行这个操作，说明这个白色石头的右边必然有至少一个红色石头（如果没有，这个操作可以不做）
    那么就可以将这个操作序列中这步，改为将这个白色石头与其右边的红色石头交换
  • 将某个石头有红色变为白色
    同理，其左边至少有一个白色石头，可以将这步改为交换
• 那么我们就得到了一个只由交换操作构成的序列

所以我们只需要双指针跑一下，具体：
初始时，第一个指针在最左边，第二个指针在最右边
循环：
第一个指针向右跑，找白色石头；第二个指针向左跑，找红色石头
如果都找到后，第一个指针在第二个指针左边，则交换这两个石头
直到第一个指针跑到第二个指针右边，跳出循环
（和快速排序里的代码几乎是一样的）

时间复杂度

两个指针，
最坏情况下，每个指针会将整个序列遍历一遍
故时间复杂度为 $O(2n) = O(n)$

C++ 代码

#include <cstdio>
#include <cstring>

// n 为序列长度，cnt 为操作数量，str 为读入的序列
int n, cnt;
char str[200005];

int main()
{
    scanf("%d\n%s", &n, str);
    // 这里第一个指针指向最左边的左边，第二个指针指向最右边的右边，会好写一些
    int i = -1, j = n;
    while (i < j)
    {
        while ( ++ i < j && str[i] != 'W'); // 当 i ++ 后在 j 左边，且没找到 'W'，则继续循环
        while ( -- j > i && str[j] != 'R'); // 当 j -- 后在 i 右边，且没找到 'R'，则继续循环
        if (i < j) cnt ++ ;                 // 如果都找到后 i < j，则 交换次数 ++ ，
        // 这行空出来是用来补充上一行注释的 // 这里并不需要真正地维护操作，只需要记录操作数量即可。
    }
    printf("%d\n", cnt);
    return 0;
}

$$ $$