文字列スワップ [パソコン甲子園2017 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0365?year=2017

前提知識

• BIT

考察過程

1. 辞書順最小の文字列を構築するテク「貪欲に先頭から決めていく」
2. ある文字をスワップして先頭にもってくるためには、その文字より前にある文字数分だけスワップが必要になる
3. BITを使えば使った文字を消した状態で、ある文字より前にある文字数をカウントできる
4. これでいいの？と思うが、書いて流すと通る

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0365/review/3136717/hamayanhamayan/C++14

2つのデータ構造を使って、先頭から順番に文字を決定していく。
　
idx[c] := 文字cがある添字のキュー（昇順で入ってる）
これを使って、各文字について一番先頭に近い添字を取ってくる。

BITを使って、使われた文字と使われていない文字を判別。　
bit[i] := i番目の文字が使われていれば0, 残っていれば1
　
先頭の文字を'a'～'z'まで順番に持ってこれるか試す。
まずidx[c]を使って、その文字で先頭に近い添字を持ってくる（変数top）。
この文字を先頭に持ってくるにはbit[0,top]文字分スワップする必要がある（スワップ回数req）。
もしスワップ回数がK以下であれば実現可能なので、実現する。
これを繰り返す。

string S; int K;
queue<int> idx[26];
BIT<int> bit;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> K;
    int N = S.length();
    bit.init(N);
    rep(i, 0, N) idx[S[i] - 'a'].push(i);
    rep(i, 0, N) bit.add(i, 1);

    string ans = "";
    rep(i, 0, N) rep(c, 0, 26) if (0 < idx[c].size()) {
        int top = idx[c].front();
        int req = bit.get(0, top);
        if (req <= K) {
            ans += char('a' + c);
            idx[c].pop();
            K -= req;
            bit.add(top, -1);
            break;
        }
    }
    cout << ans << endl;
}