hihocoder hiho一下 第164周 有序01字符串

题目链接:http://hihocoder.com/contest/hiho164/problem/1

题意:略。

思路:枚举每个点看前面全变成0后面全变成1需要的操作数然后更新答案即可,时间复杂度O(n^{2}),更优的办法是我们预处理出前缀1的个数和后缀0的个数,然后再进行更新,时间复杂度O(n)

#include <bits/stdc++.h>
using namespace std;
int T;
char s[1005];
int main(){
    for (scanf("%d",&T);T--;){
        scanf("%s",s);
        int ans=2000,len=strlen(s);
        for (int i=0;i<len;i++){
            int tmp=0;
            for (int j=i-1;j>=0;j--) tmp+=s[j]=='1';
            for (int j=i+1;j<len;j++) tmp+=s[j]=='0';
            ans=min(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

第二种:

#include <bits/stdc++.h>
using namespace std;
int T,pre[1005],suff[1005];
char s[1005];
int main(){
    for (scanf("%d",&T);T--;){
        scanf("%s",s+1);
        int ans=2000,len=strlen(s+1);
        pre[0]=suff[len+1]=0;
        pre[1]=s[1]=='1';suff[len]=s[len]=='0';
        for (int i=2;i<=len;i++) pre[i]=pre[i-1]+(s[i]=='1');
        for (int i=len-1;i>=1;i--) suff[i]=suff[i+1]+(s[i]=='0');
        for (int i=1;i<=len;i++) ans=min(ans,pre[i-1]+suff[i+1]);
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注