4.3 小明的爱好

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

为了排解巨大的学习压力，小明养成了一个奇特的爱好：在宿舍养蚂蚁。

小明养了两种颜色的蚂蚁：红色和黑色。这一天，他把他所有的蚂蚁排成一列。但他发现这样的队伍看上去颜色杂乱不美观。

小明的目标是使得队伍中的蚂蚁颜色红黑相间（即第一只红，第二只黑，第三只红……；或第一只黑，第二只红，第三只黑……）。为了达到这个目标，他可以在每一步选用以下任一种方法：1. 交换任意两只蚂蚁的位置；2.用水彩笔将任意一只蚂蚁涂成红色或黑色。

小明想用尽量少的步骤，使得蚂蚁的颜色红黑相间，请你帮帮他。

数据输入

输入第一行为正整数\(n\)，表示蚂蚁的个数。接下去\(n\)个字符，表示排成一列的蚂蚁的颜色，‘r’ 表示红色，‘b’ 表示黑色。

数据输出

输出一个数，表示最少的操作次数。

输入示例 输出示例
5
rbbrr		 1
5
bbbbb		 2

数据范围

\(70\%\)的得分点，\(n \leq 10\)；\(30\%\)的得分点，\(n \leq 100000\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
inline int min(int a, int b){ return a < b ? a : b; }
inline int max(int a, int b){ return a < b ? b : a; }

int main(){
    int n, i;
    int oddr = 0, evenb = 0, oddb = 0, evenr = 0;
    char anti;
    for (i = 0; i < n; ++i){
        anti = getchar();
        if (i % 2 && anti == 'r')++evenr;
        else if (i % 2 && anti == 'b')++evenb;
        else if (anti == 'r')++oddr;
        else ++oddb;
    }
    getchar();
    printf("%d\n", min(max(oddr, evenb), max(oddb, evenr)));
    return 0;
}

设计思路与复杂度分析

计算原串变成目标串“\(brbrb\cdots\)”的最少操作数\(res1\)。计算原串变成目标串“\(rbrbr\cdots\)”的最少操作数\(res2\)。最终的答案\(res=min(res1,res2)\)。

怎么计算最少操作数？统计位于\(r\)（目标串）的位置上的\(b\)（原串），记作\(sumb\)。统计位于\(b\)（目标串）的位置上的\(r\)（原串），记作\(sumr\)。我们最少需要进行\(min(sumb,sumr)\)次交换\(+|sumb-sumr|\)次替换。分析上面的式子得\(res=max(sumb,sumr)\)。时间复杂度\(O(n)\)、空间复杂度\(O(n)\)。

贪心策略：对于已经在正确的位置上的字符，我们没有必要动它，因为这样做不会减少操作数。对于错误位置上的字符，我们肯定优先交换，剩下的不能交换的再替换。因为交换能摆正两个位置，而替换只能摆正一个位置。

0%