CodeForces - 1256D Binary String Minimizing

 1 #include <iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 #include<cstdio>
 8 #define ll long long
 9 using namespace std;
10 const int N = 1e6 + 10;
11 int main()
12 {
13     ll q, n, k, i, j;
14     char a[N];//数组a存下字符串
15 
16     scanf("%lld",&q);
17 
18     for( i = 1; i <= q; i ++)
19     {
20         memset(a,0,sizeof(a));
21         queue<ll>b;
22         ll first = 0,flag = 0;
23         scanf("%lld%lld",&n,&k);
24         for( j = 1; j <= n; j ++)
25         {
26             scanf(" %c",&a[j]);
27             if(a[j] == ‘0‘ && flag != 0)//flag != 0的条件是前置因为0就可以不用管了
28             {
29                 b.push(j);//把非前置0的位置传进去队列
30             }
31             else if(flag == 0&&a[j] == ‘1‘)
32             {
33                 flag = j;//记下第一个1的位置
34             }
35         }
36         first = flag;
37 
38         while(k > 0&&!b.empty())
39         {
40             //当k足够一次性将后面的0和第一个1调换的时候
41             if(k - (b.front()-first) >= 0)
42             {
43                 k = k -(b.front()-first);//更新k
44                 swap(a[first],a[b.front()]);
45                 b.pop();//把第一个提出队列
46                 first ++;//下一个1肯定跟在第一个后面，可以自行纸上模拟一下
47             }
48             //如果不行，就调换到最大可调的地方
49             else
50             {
51                 swap(a[b.front() - k],a[b.front()]);
52                 break;
53             }
54         }
55         //按顺序输出
56         for( j = 1; j <= n ; j ++)
57         {
58             printf("%c",a[j]);
59         }
60         printf("\n");
61     }
62     return 0;
63 }