题目地址：

给定一个01串（仅由‘ 0’或‘1’组成的字符串），现在想把这个数字串排序成“非递减”有序序列，请问至少需要多少次交换（任意两个位置交换）？ 

输入描述:

输入数据第一行是一个正整数T(T<=100),表示有T组测试数据；接下来的T行，每行给出01串。数据保证——50%的字符串长度在[1,100 ]95%的字符串长度在[1,10000]100%的字符串长度在[1,1000000]

输出描述:

对于每组测试数据，请输出排成“非递减有序序列”的最小交换次数。每组输出占一行。

 

输入例子:

30110110

输出例子:

011 题解：

因为输入的序列仅由0和1组成，现在要求排序成非递减序列，即”0”全部在左边，“1”全部在右边。 所以可以统计a[i]中"0"的个数num，那么从0到num中如果存在“1”，就必然存在一次交换，统计的从0到num中"1"的数量即为答案。 时间复杂度O(n)。100%数据规模max_length=1e6，可以AC。 代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int N=1e6+131; 6 char a[N]; 7 int num; 8  9 int main()10 {11     int T;12     13     scanf("%d",&T);14     while(T--) {15         num=0;16         scanf("%s",a);17         int len=strlen(a);18         for(int i=0;i