PIPIOJ 1478 题解：PIPI 的翻转游戏（最少翻转次数）

题目链接：http://pipioj.online/problem.php?id=1478

题意重述

给一个长度为 n 的 01 串，每次可以翻转任意一位（0<->1）。
目标是把字符串变成：前面全是 0，后面全是 1（两段都允许为空，但不能同时为空）。

问最少翻转多少次。

思路

把最终字符串看成在某个位置 i 切开：

• 左半段 s[0..i-1] 必须全是 0
• 右半段 s[i..n-1] 必须全是 1

那么以 i 为分割点时，需要翻转：

• 左边所有 1（把它们变成 0）
• 右边所有 0（把它们变成 1）

即：

cost(i) = prefixOne[i] + suffixZero[i]

答案就是所有 i in [0, n] 中的最小值。

实现细节

1. 先统计整串 0 的总数，作为初始 suffixZero（分割点在最左边）。
2. 从左到右移动分割点：
   • 经过一个 1，prefixOne++
   • 经过一个 0，suffixZero--
3. 每一步更新最小值。

时间复杂度 O(n)，空间复杂度 O(1)。

C++17 代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    if (!(cin >> n >> s)) return 0;

    int suffixZero = 0;
    for (char c : s) {
        if (c == '0') ++suffixZero;
    }

    int prefixOne = 0;
    int ans = prefixOne + suffixZero; // i = 0

    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') {
            ++prefixOne;
        } else {
            --suffixZero;
        }
        ans = min(ans, prefixOne + suffixZero); // i = i+1
    }

    cout << ans << '\n';
    return 0;
}

样例解释

输入：

6
010110

分割在不同位置时，最小代价为 2，所以输出：

2

易错点

1. 分割点一共有 n+1 个（包含最左和最右）。
2. 题目允许全 0 或全 1，正好对应分割点在最右或最左。
3. 输入规模到 1e5，O(n^2) 会超时，必须线性做法。