hiho #1326 : 有序01字符串

#1326 : 有序01字符串

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

输入

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

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

输出

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

样例输入

样例输出

0
1
1

AC代码：

 1 #include "iostream"
 2 #include "string.h"
 3 #include "algorithm"
 4 #define MAX 1001
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int t;
10     char s[MAX];
11 
12     cin >> t;
13     while (t--)
14     {
15         int l, cnt0, cnt1;
16         int ans=1000000;
17 
18         cin >> s;
19         
20         l = strlen(s);
21         for (int i = 0; i <= l;i++)
22         {
23             cnt0 = cnt1 = 0;
24             for (int j = i - 1; j >= 0; j--)
25             {                
26                 cnt0 += (s[j] == '0' ? 0 : 1);
27             }
28             for (int j = i; j < l; j++)
29             {                
30                 cnt1 += (s[j] == '1' ? 0 : 1);
31             }
32             ans = min(ans, cnt1 + cnt0);
33 
34         }
35         cout << ans << endl;;
36     }
37 }