题解 | 反转硬币

import java.math.BigInteger;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] b = new int[n];
        String s = in.next();

        for (int i = 0; i < n; i++) {
            b[i] = (s.charAt(i) == '1') ? 1 : 0;
        }

        /** 算法设计依据
         * (1) 000…01（n位）--(n-1)次--> 111…11 --n次--> 000…00
         * (2) 假定序列[…]需要x次操作变为[0…0]（全0），有
         *     I. 1[…]--x次-->1[0…0]
         *     II. 0[…]00…01--x次-->0[0…0]00…01
         *     因此，较长序列的处理可以递归地转化到子序列的处理上
         * (3) 序列的后缀0可以忽略
         */

        int left = 0;
        int right = b.length;

        // 双指针遍历数组
        while (left < right) {
            if (b[left] == 0) {
                // 如果左指针指向0，则需要找到右侧最近的1来配对
                right--; // 右指针左移

                // 继续移动右指针直到找到1或与左指针相遇
                while (right > left && b[right] != 1) {
                    right--;
                }

                // 如果左右指针相遇，说明没有可配对的1，结束循环
                if (right == left) {
                    break;
                }

                // 计算当前0和右侧1之间的距离（包含两端）
                int distance = right - left + 1;
                b[left] = -distance; // 在左指针位置标记负的距离值
            }
            left++; // 左指针右移
        }

        // 计算最终结果
        BigInteger t = BigInteger.ZERO;
        // 从右向左遍历处理后的数组
        for (int i = left - 1; i >= 0; i--) {
            if (b[i] > 0) {
                // 遇到1，结果加1
                t = t.add(BigInteger.ONE);
            } else {
                // 遇到标记的负距离值，计算对应的贡献值
                // 公式：-b[i] * 2 - 1（因为距离为d时贡献值为2d-1）
                t = t.add(BigInteger.valueOf(-b[i] * 2 - 1));
            }
        }
        System.out.println(t); // 输出最终结果
    }
}