leetcode1505 最多 K 次交换相邻数位后得到的最小整数

思路：

贪心的思路不难想到，关键是如何使用树状数组优化。参考了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;
    }
};