Submission #1514056

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <set>

using namespace std;

typedef std::numeric_limits<double> dbl;

//#define DEBUG

int main()
{
        int N, K;
        string S;
        cin >> N >> K;
        cin >> S;

        if (K == 0) {
            cout << S << endl;
            return 0;
        }

        priority_queue<char, vector<char>, greater<char>> pq;
        for (int i = 0; i < N; ++i) {
            pq.push(S[i]);
        }

        for (int matchNum = N; matchNum != 0; --matchNum) {
            priority_queue<char, vector<char>, greater<char>> cp = pq;
            string ans = "";
            int unmatchNum = 0;
            for (int i = 0; i < matchNum; ++i) {
                int c = cp.top();
                if (S[i] != c)
                    unmatchNum++;
                ans.push_back(c);
                cp.pop();
            }

            multiset<char> rest;
            for (int i = 0; i < N - matchNum; ++i) {
                char c = cp.top();
                //cout << "   " << cp.size() << " " << c << endl;
                rest.insert(c);
                cp.pop();
            }

            for (int i = matchNum; i < N; ++i) {
                char c = S[i];
                //cout << "match: " << c << endl;
                auto itr = rest.find(c);
                if (itr == rest.end()) {
                    unmatchNum++;
                    ans += "#";
                    continue;
                }
                ans.push_back(c);
                rest.erase(itr);
            }

            vector<char> bond;
            for (auto r : rest) {
                bond.push_back(r);
            }
            vector<char>::const_iterator bitr = bond.begin();
            for (auto& c : ans) {
                if (c == '#')
                    c = *(bitr++);
            }

            if (unmatchNum <= K) {
                cout << ans << endl;
                return 0;
            }
            
        }

        return 0;
}

Submission Info

Judge Result