AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 题解

· · 题解

题目传送门

根据字典序的性质，容易想到，在字典序最小的时候，一定以 a 开头，但是此时我们要保证字典序最大，那么后面就紧跟的是 c，然后再是 b。

这是字符的拼接，我们可以考虑扩展到字符串的拼接：我们可以由 3 个局部最优的字符串拼接成一个新的字符串，然后再和其它字符串进行匹配。

此时我们只需要讨论 3 个的情况：有 s_1,s_2,s_3，为了方便，我们可以令 s_1<s_2<s_3。那么我们通过上面的方式，最小的后面接最大的，那么我们得到的序列就是 s_1s_3s_2，如果还有一个字符串 s_3<s_4，那么我们可以将原来的字符串分为 s_1,s_3s_2，那么 s_4 就是接在 s_1 后面的，然后是 s_3，最后是 s_2……

那么，我们发现规律，每次有字符串集取最大和最小拼接在一起，然后再和其它字符串匹配。这个结论可以用数学归纳法证明：

上文已经证明了 s_1s_3s_2 的正确性，那么对于 k，上述规律成立。现在我们有：s_1s_k\cdots s_2，和一个新串 s_{k+1}，此时 s_1 一定放在最前面，由于 s_k<s_{k+1}，那么无论如何，s_k 加上后面那一坨都是 <s_{k+1} 的，那么我们可以将 s_k\cdots s_2 想象成一个整体，按照上面的方式，就是 s_2，s_{k+1} 是 s_3，那么此时答案由上面的方式，就是 s_1s_{k+1}s_k\cdots s_2，那么对于 k+1 成立，所以结论成立。

同时取最大和最小，用 std::multiset 维护，时间复杂度 O((X+Y+Z)\log(X+Y+Z))。

#include<bits/stdc++.h>
using namespace std;
multiset<string> s;
int a,b,c;
int main(){
    cin>>a>>b>>c;
    while(a--) s.insert("a");
    while(b--) s.insert("b");
    while(c--) s.insert("c");
    while(s.size()>1){
        auto a=s.begin(),b=(--s.end());
        s.insert((*a)+(*b)),s.erase(b),s.erase(a);
    }
    cout<<(*s.begin())<<endl;
    return 0;
}