题目描述：
给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：
- 选中一个下标
i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。 - 选中一个下标
i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。
返回使字符串内所有字符 相等 需要的 最小成本 。
反转 字符意味着：如果原来的值是 ‘0’ ，则反转后值变为 ‘1’ ，反之亦然。
数据范围：
$1\le s.len \le 10^5, s[i]$ 为 $0$ 或 $1$
题解：
假设 $[0, i - 1]$ 全都一样了， $s[i - 1] \neq s[i]$ 那么需要将 $[0,i]$ 搞的全一样，可以将 $[0,i-1]$ 翻转，成本为 $i$ ；也可以翻转 $[i,n - 1]$ ，成本为 $n - i$ ，两者取最小值。
代码：
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
27
28
29
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const static long long mod = 1e9 + 7;
long long minimumCost(string s)
{
int n = s.length();
int ans = 0;
for (int i = 1; i < n; ++i)
{
if (s[i - 1] != s[i])
{
ans += min(i, n - i);
}
}
return ans;
}
};
|