GCJ 2016 Round 1A A: The Last Word
解法
S[0]〜S[N-1] を並び替えるとき、S[0]から見て外側にあるほどS[i]のiは大きくなる。ちゃんと書くと、最終的な単語の先頭部分 S[i]S[j]S[k]...S[0] においてi>j>k>...>0 が成り立たなければならない。同様に末尾のS[0]S[l]S[m]...においては0
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; string solve(const string &S) { vector<char> prefix, suffix; prefix.push_back(S[0]); for (int i = 1; i < S.size(); ++i) if (S[i] >= prefix.back()) prefix.push_back(S[i]); else suffix.push_back(S[i]); reverse(prefix.begin(), prefix.end()); string p(prefix.begin(),prefix.end()); string s(suffix.begin(),suffix.end()); return (p + s); } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; for (int testcase = 1; testcase <= T; ++testcase) { string S; cin >> S; string ans = solve(S); cout << "Case #" << testcase << ": "; cout << ans << endl; } }