用C语言写出程序:一个长度为n的01串,你可以删除这个串的一个前缀和一个后缀(可以为空),既保留一个原串的连续子串, 操作之后整个串的代价为下面两部分之和:1、被删除的字符1的个数。2、剩下的字串的字符0的个数。你需要最小化代价,并将其输出
时间: 2024-05-15 10:18:30 浏览: 77
我会尽力回答您的问题。关于您提出的问题,以下是一种可能的求解方法:
假设原给出的01串为s,我们需要找到一个位置i,使得s的前i个字符和后j个字符(或者只有前i个或只有后j个)可以组成一个连续子串,且删除前缀和后缀后,剩下的字串中0的个数最多。我们可以枚举i,然后分别计算出区间[1,i]和[i+1,n]中分别有多少0和1,然后取两者的最小值作为删除代价,并将两者的和作为该方案的总代价。最后找到总代价最小的一个i即可。
下面是C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
char s[100005];
scanf("%d %s", &n, s+1);
int i, j, cnt1, cnt0, ans=n;
cnt1 = cnt0 = 0;
for(i=1; i<=n; i++)
{
if(s[i] == '1')
{
cnt1++;
}
else
{
cnt0++;
}
j = n - i + 1;
int cur = (cnt1 < cnt0) ? cnt1 : cnt0;
int del = cnt1 + cnt0 - cur * 2;
if(del < ans)
{
ans = del;
}
}
printf("%d\n", ans);
return 0;
}
```
此代码可以求出01串中最小的代价,并将其输出。如果您还有其他问题,欢迎随时提出。
阅读全文