思路：
贪心的思路不难想到，关键是如何使用树状数组优化。参考了https://leetcode-cn.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/solution/zui-duo-k-ci-jiao-huan-xiang-lin-shu-wei-hou-de-da/
实现：
class BIT { private: vector<int> bit; public: BIT(int n) { bit.resize(n); } inline int lowbit(int x) { return x & -x; } void add(int i, int x) { while (i < bit.size()) { bit[i] += x; i += lowbit(i); } } int sum(int i) { int ans = 0; while (i) { ans += bit[i]; i -= lowbit(i); } return ans; } }; class Solution { public: string minInteger(string num, int k) { int n = num.size(); int N = n + 2; BIT bit(N); vector<queue<int>> p(10, queue<int>()); for (int i = 0; i < n; i++) { int x = num[i] - ‘0‘; p[x].push(i + 1); } string res = ""; int cnt = 0; vector<bool> vis(n, false); while (k and cnt < n) { int i = 0; for ( ; i < 10; i++) { if (p[i].empty()) continue; int x = p[i].front(); int cost = x - 1 + bit.sum(N - 1) - bit.sum(x) - cnt; if (cost <= k) { bit.add(x, 1); k -= cost; p[i].pop(); res += char(‘0‘ + i); vis[x - 1] = true; break; } } cnt++; } for (int i = 0; i < n; i++) { if (vis[i]) continue; res += num[i]; } return res; } };