Input
3 8 5 11011010 7 9 1111100 7 11 1111100
Output
01011110 0101111 0011111
题意：t组样例，给一个长度为n的字符串，要求在k步以内进行字符交换（1步只能交换i和i+1）使得字符串字典序最小。
思路：贪心，存下0的位置，让前面的0尽可能往前移，然后就是模拟计算操作。
#pragma comment(linker, "/STACK:1024000000,1024000000") #pragma GCC optimize(2) #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<cmath> #include<string> #include<map> #include<vector> #include<ctime> using namespace std; #define mm(a,b) memset(a,b,sizeof(a)) typedef long long ll; const int maxn = 1e6+10;; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; int gcd(int a,int b) {if(b==0) return a;return gcd(b,a%b);} char s[maxn]; int main(){ int q; scanf("%d",&q); while(q--) { vector<int>v; int n; ll k; scanf("%d %lld",&n,&k); scanf("%s",s); for(int i=0;i<n;i++) { if(s[i]=='0') v.push_back(i); } int len=v.size(); if(v.size()==n||v.size()==0) { printf("%s ",s); continue; } int pos1=0,pos2=0; while(k>0&&pos2<len&&pos1<=n-1) { if(s[pos1]=='0') { pos1++; } else if(v[pos2]<=pos1) { pos2++; } else { int cnt=v[pos2]-pos1; if(k<cnt) { pos1=v[pos2]-k; k=0; } else k=k-(cnt); s[pos1]='0'; s[v[pos2]]='1'; pos1++; pos2++; } } printf("%s ",s); } return 0; } /* 9 8 1 11011010 8 2 11011010 8 3 11011010 8 4 11011010 8 5 11011010 8 6 11011010 8 7 11011010 8 10 11011010 8 50 11011010 */