反转硬币__牛客网

天天摸鱼的奇亚籽很想按时下班

C++解法，使用两个vector预先收集需要处理的位置。这题目有点像不撞南墙不回头的意思

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

int main() {
    int a;
    cin>>a;
    string str;
    cin>>str;
    int p = -1;
    for(auto c:str){
        if(c=='1') p++;
    }
    if(p==-1) return 0;
    vector<int> zeros;
    for(int i=0;i<p;i++){
        if(str[i]=='0') zeros.push_back(i);
    }
    vector<int> ones;
    for(int i=a-1;i>p;i--){
        if(str[i]=='1') ones.push_back(i);
    }
    int myi = zeros.size()-1;
    int myj = ones.size()-1;
    long res = 0;
    while(myi>=0||myj>=0){
        if(str[p]=='1'){
            if(myi<0){
                cout<<-1<<endl;
                return 0;
            }
            int temp = zeros[myi];
            res +=p-temp;
            p  =temp;
            myi--;
        }else{
            if(myj<0){
                cout<<-1<<endl;
                return 0;
            }
            int temp = ones[myj];
            res +=temp-p;
            p = temp;
            myj--;
        }
    }
    res += p+1;
    cout << res << endl;
}

发表于 2025-04-27 20:25:38 回复(0)

牛客602717397号

```python

importsys

def f():

n = int(input())

s = input()

res = 0

p = -1

one,zero = [],[]

fori in range(n):p+=1ifs[i] == '1'else0

ifp == -1:return0

fori in range(n-1,p,-1):

ifs[i] == '1': one.append(i)

fori in range(p):

ifs[i] == '0': zero.append(i)

lo,lz = len(one),len(zero)

i,j = lz-1,lo-1

whilei>=0or j>=0:

ifs[p] == '1':

ifi < 0: return-1

res+= p-zero[i]

p = zero[i]

i-=1

else:

ifj < 0:return-1

res+= one[j]-p

p = one[j]

j-=1

res+=p+1

returnres

print(f())

```

发表于 2025-04-18 13:18:27 回复(0)

Java

美丽的布莱恩想要offer

思路和另外几位略有差异
通过基本法则确立了序列需要的步骤数和子序列所需步骤数的关系，一开始采用了递归的想法，但在具体实现时又去掉了递归转为while循环

(1) 000…01（n位）--(n-1)次--> 111…11 --n次--> 000…00

(2) 假定序列[…]需要x次操作变为[0…0]（全0），有

I. 11…11[…]--x次-->11…11[0…0]

II. 0[…]00…01--x次-->0[0…0]00…01

因此，较长序列的处理可以递归地转化到子序列的处理上

(3) 序列的后缀0可以忽略

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); // 输出最终结果
    }
}

发表于 2025-06-16 22:27:04 回复(0)

Pypy3

牛客229155584号

这题不会有死循环，纯误导了

发表于 2025-05-21 19:59:16 回复(0)

反转硬币

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题