2712. 使所有字符相等的最小成本

2712. 使所有字符相等的最小成本

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。
1
2

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 ‘0’ ，则反转后值变为 ‘1’ ，反之亦然。

示例 1：

输入：s = “0011”
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = “0000” ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = “010101”
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = “101101” ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = “011101” ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = “111101” ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = “111110” ，成本为 2 。
执行第一种操作，选中下标 i = 5 ，可以得到 s = “111111” ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。

这题其实比较特别，我也是看别人思路才做出来的，这题的关键在于，没碰到一个0-1的相邻对，我们就一定要采取一定的方法去解决，但是在我们处理这个0-1相邻对时，其他的相邻0-1对是不受影响的，所以遵循这个原理，我们就可以去写出自己的代码。
原则上，以处理每个0-1相邻对最少次数为优先，解题代码如下：

long long fminz(int a,int b){
    if(a>b){
        return b;
    }
    return a;
}


long long minimumCost(char * s){

    long long sum_reverse=0;
    int n=strlen(s);
    
    for(int i=0;s[i]!='\0';i++){
        if(s[i+1]!='\0'){
            if(s[i]!=s[i+1]){
                sum_reverse=sum_reverse+fminz(i+1,n-i-1);

            }

        }
        
    }
    return sum_reverse;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26