No.205 マージして辞書順最小 - yukicoder
- 貪欲法。priority_queue で書くより set で書く方が綺麗にかけたかも。priority_queue の compare 関数がうまく実装できなかった...。
class MergeAndLexicographicOrderSort
{
public:
void solve(void)
{
int N;
cin>>N;
auto lex_comp = [](string a, string b) {
return b<a;
};
priority_queue<string,vector<string>,decltype(lex_comp)> S(lex_comp);
REP(i,N)
{
string s;
cin>>s;
S.push(s+'~');
}
string T;
while (!S.empty())
{
string s = S.top();
S.pop();
T += s[0];
s = s.substr(1);
if (s.length() > 1)
S.push(s);
}
cout<<T<<endl;
}
};