反转硬币

思路

拿到这道题，我们先搞清楚规则：桌上有 $n$ 个硬币，0 表示正面，1 表示反面。每一步，数一下当前有多少个反面朝上的硬币，假设是 $k$ 个，就把第 $k$ 个位置的硬币翻转。重复这个过程，直到所有硬币都变成正面（全 0）。

直接模拟的话，每一步 $k$ 要么加 1 要么减 1，总步数可能达到 $O(n^2)$ 级别，对于 $n$ 接近 $10^5$ 的数据会超时。

那怎么优化呢？我们换个视角来理解这个过程。

把 $k$ 值的变化想象成一个"行走"的过程：从初始的 $k_0$ 出发，目标是走到 $0$ 。每到一个位置 $k$ ，看一眼 coins[ $k-1$ ]：

如果是 1（反面），就能"通过"这一层，往下走到 $k-1$ ，同时把它翻成 0；
如果是 0（正面），就会被"弹回去"，往上走到 $k+1$ ，同时把它翻成 1。

对于被弹回的情况，我们需要在上面转一圈再回来。回来之后，这个位置已经变成 1 了，就能顺利通过。

关键观察来了：当位置 $k-1$ 是 0 时，我们要往上找到第一个 1 的位置 $j$ （从位置 $k$ 开始往上扫）。中间经过的都是 0，一路弹上去再弹回来，总代价是 $2(j-k)+3$ 。而这一过程结束后，位置 $j$ 的 1 被消耗掉了（变成 0），其余中间位置恢复原状。

于是算法就清晰了：用一个有序集合维护所有 1 的位置。从 $k_0$ 开始逐层下降：

如果 $k-1$ 在集合中（是 1），直接移除，代价 $1$ ， $k$ 减 $1$ ；
否则，在集合中查找 $\geq k$ 的最小元素 $j$ ，代价 $2(j-k)+3$ ，移除 $j$ ， $k$ 减 $1$ 。

每层只做一次集合查询和删除，总时间 $O(n \log n)$ 。

另外可以证明， $k$ 的值永远不会超过 $n$ （因为最多 $n$ 个硬币），且当 coins[ $k-1$ ] 为 0 时， $k$ 以上必定存在 1（否则 $k$ 个 1 无法放进 $k-1$ 个位置里），所以过程一定能终止，不存在"不可能"的情况。

代码

C++
Java

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

int main() {
    int n;
    scanf("%d", &n);
    char s[100005];
    scanf("%s", s);

    set<int> ones;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') ones.insert(i);
    }

    int k = (int)ones.size();
    long long total = 0;

    while (k > 0) {
        auto it = ones.find(k - 1);
        if (it != ones.end()) {
            ones.erase(it);
            total += 1;
            k--;
        } else {
            auto it2 = ones.lower_bound(k);
            int j = *it2;
            total += 2LL * (j - k) + 3;
            ones.erase(it2);
            k--;
        }
    }

    printf("%lld\n", total);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();

        TreeSet<Integer> ones = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') ones.add(i);
        }

        int k = ones.size();
        long total = 0;

        while (k > 0) {
            if (ones.contains(k - 1)) {
                ones.remove(k - 1);
                total += 1;
                k--;
            } else {
                int j = ones.ceiling(k);
                total += 2L * (j - k) + 3;
                ones.remove(j);
                k--;
            }
        }

        System.out.println(total);
    }
}

复杂度分析

时间复杂度： $O(n \log n)$ 。初始化有序集合 $O(n \log n)$ ，之后每层下降做一次集合查询和删除，共 $k_0 \leq n$ 层，每次 $O(\log n)$ 。
空间复杂度： $O(n)$ ，存储有序集合。