CodeForces 254C Anagram

http://codeforces.com/problemset/problem/254/C
本番ではとけなかった問題。

いいかんじにやったらできる。
アルゴリズムとしては、おきかえなければならないか、もしくは今よりも小さいなら置き換える。
queueとlower_boundをつかってるのが個人的ポイント。

#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <algorithm>

#include <functional>
#include <cctype>

#include <complex>
#include <string>
#include <sstream>

#define pb push_back
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()

#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container),element) != container.end())
#define sz(a) ((int)a.size())

typedef long long ll;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;

using namespace std;

int main(){
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    string s,t;
    int n;
    fin >> s >> t;
    n = s.length();
    map<char,int> diff;
    map<char,vector<int> > m;
    for(int i=0;i<n;i++){
        diff[s[i]]--;
        m[s[i]].push_back(i);
        diff[t[i]]++;
    }

    queue<char> toadd;
    for(char c = 'A';c<='Z';c++){
        rep(i,diff[c]){
            toadd.push(c);
        }
    }

    int cnt = 0;
    rep(i,n){
        if(diff[s[i]] < 0){
            if(toadd.front() < s[i] or
               m[s[i]].end() - lower_bound(all(m[s[i]]),i) == -diff[s[i]]) {
                cnt++;
                diff[s[i]]++;
                s[i] = toadd.front();
                toadd.pop();
            }
        }
    }
    fout << cnt << endl;
    fout << s << endl;
    return 0;
}