hiho #1326 : 有序01字符串

#1326 : 有序01字符串

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

对于一个01字符串，你每次可以将一个0修改成1，或者将一个1修改成0。那么，你最少需要修改多少次才能把一个01串  变为有序01字符串(有序01字符串是指满足所有0在所有1之前的01串)呢？

输入

第一行是一个整数 ，代表测试数据的组数。(1 ≤  ≤ 10)

以下T行每行包含一个01串  。(1 ≤ || ≤ 1000)

输出

对于每组测试数据输出最少需要修改的次数。

样例输入

3

000111

010001

100000 

样例输出

0

1

1

AC代码：

 #include "iostream"

 #include "string.h"

 #include "algorithm"

 #define MAX 1001

 using namespace std;

 int main()

 {

     int t;

     char s[MAX];

     cin >> t;

     while (t--)

     {

         int l, cnt0, cnt1;

         int ans=;

         cin >> s;

         l = strlen(s);

         for (int i = ; i <= l;i++)

         {

             cnt0 = cnt1 = ;

             for (int j = i - ; j >= ; j--)

             {

                 cnt0 += (s[j] == '' ?  : );

             }

             for (int j = i; j < l; j++)

             {

                 cnt1 += (s[j] == '' ?  : );

             }

             ans = min(ans, cnt1 + cnt0);

         }

         cout << ans << endl;;

     }

 }