这是一道比较典型的贪心算法题目。我们可以先统计字符串中 0 和 1 的个数,因为最终要将所有字符变为相等的,所以我们只需要考虑将其变为 0 或者 1 即可。如果字符串中 0 的个数比 1 的个数多,那么我们就让所有字符都变为 0,否则就让所有字符都变为 1。 接下来,我们可以考虑如何使得成本最小。假设我们将所有字符都变为 0,那么可以发现,对于每个下标 i,如果当前位置是 0,那么我们就不需要将其反转;如果当前位置是 1,那么我们需要将从下标 0 到下标 i 的所有字符都反转,这样可以让当前位置变为 0。因此,对于每个位置 i,我们只需要计算将从下标 0 到下标 i 的所有字符反转的成本即可。 同理,如果我们将所有字符都变为 1,那么对于每个位置 i,我们只需要计算将从下标 i 到下标 n-1 的所有字符反转的成本即可。 最后,我们只需要比较两种情况的成本,取最小值即可。时间复杂度为 O(n)。用c语言写
时间: 2024-02-13 14:05:27 浏览: 17
数据结构与算法课设题目一1 (2).docx
好的,以下是用C语言实现上述算法的代码:
```c
#include <stdio.h>
#include <string.h>
int min(int a, int b) {
return a < b ? a : b;
}
int minCost(char *s) {
int n = strlen(s);
int cnt[2] = {0}; // 统计0和1的个数
for (int i = 0; i < n; i++) {
cnt[s[i] - '0']++;
}
if (cnt[0] == n || cnt[1] == n) return 0; // 如果所有字符都相同,则成本为0
int ans = n;
for (int k = 0; k <= 1; k++) {
int cur = 0; // 当前操作的位置
int cost = 0; // 当前操作的总成本
for (int i = 0; i < n; i++) {
if (s[i] - '0' != k) {
cost += i + 1 - cur; // 计算反转前半段的成本
cur = i + 1; // 更新当前操作的位置
}
}
cost += n - cur; // 计算反转后半段的成本
ans = min(ans, cost); // 取两种情况的最小值
}
return ans;
}
int main() {
char s[] = "1010101";
int ans = minCost(s);
printf("%d\n", ans); // 输出最小成本
return 0;
}
```
注意,这里假设输入的字符串只包含 0 和 1。如果需要处理其他字符,可以稍微修改代码。
阅读全文