贪心每次放最小的数在最前面。
每次一个数放前面后,其后面的数移动到最前面的次数就减一。
可以单点更新区间查询,或者区间更新单点查询,显然前者码量更小
const int M = 1e5+7;
class Solution {
public:char s[M]; int a[M],c[M],vs[M];vector<int>v[M];int p[M],n;void up(int x,int d){while(x<=n){c[x]+=d;x+=x&(-x);}}int qu(int x){int ans=0;while(x){ans+=c[x];x-=x&(-x);}return ans;}string minInteger(string s, int k) {n=s.length();string pr;for(int i=1;i<=n;i++){a[i]=s[i-1]-'0';v[a[i]].push_back(i);if(i>1)up(i,1);}for(int i=1;i<=n;i++){for(int j=0;j<=9;j++){if(v[j].size()<=p[j])continue;int pos=v[j][p[j]],z=qu(pos);if(z<=k){k-=z;vs[pos]=1;up(pos,-1);pr+=(a[pos]+'0'); p[j]++;break;}}}for(int i=1;i<=n;i++)if(!vs[i])pr+=(a[i]+'0');return pr;}
};