AtCoder｜Coloring Colorfully

AtCoder题解｜ABC 124C Coloring Colorfully

---

题目信息 📚

【题目描述】

$N$ tiles are arranged in a row from left to right. The initial color of each tile is represented by a string $S$ of length $N$.

The $i$-th tile from the left is painted black if the $i$-th character of $S$ is 0, and painted white if that character is 1.

You want to repaint some of the tiles black or white, so that any two adjacent tiles have different colors.

Determine the minimum number of tiles that need to be repainted to satisfy this condition.

【输入】

The input is given from Standard Input in the following format:

$S$

【输出】

Print the minimum number of tiles that need to be repainted to satisfy the condition.

【数据范围】

• $1 \leq |S| \leq 10^5$
• $S_i$ is either 0 or 1.

【输入样例1】

000

【输出样例1】

1

【输入样例2】

10010010

【输出样例2】

3

The condition can be satisfied by repainting the middle tile white.

【输入样例3】

0

【输出样例3】

0

【题目来源】

https://atcoder.jp/contests/abc124/tasks/abc124_c

---

题目解析 🍉

【题目分析】

从结果形式的角度出发，进行枚举。

$S$ 最后的形式一定为：01010101... 或者 10101010...

所以只要计算 $S$ 变成这两种结果需要多少步，取最小值即可。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    string s;
    cin >> s;

    // S -> 010101... 所需要的次数
    int ans1 = 0, num = 0;
    for (int i = 0; i < s.size(); i++) {
        char c = (char) (num + '0');
        num = 1 - num;
        ans1 += ((c == s[i]) ? 0 : 1);
    }

    // S -> 101010... 所需要的次数
    int ans2 = 0;
    num = 1;
    for (int i = 0; i < s.size(); i++) {
        char c = (char) (num + '0');
        num = 1 - num;
        ans2 += ((c == s[i]) ? 0 : 1);
    }
    cout << min(ans1, ans2) << endl;

    return 0;
}