Largest Smallest Cyclic Shift 题解

· · 题解

Largest Smallest Cyclic Shift

题目传送门

不愧为岛国黑题

解法思路

首先：答案第一位永远是最小的那个。

然后：为了让 f(T) 最大：必须让第二个是最大的。

那么第三个呢？

把最小的和最大的合并再扔回去，然后，其中最小的是不是还在最前面？那我们还是要让最大的接在后面再并起来...

这不就是合并果子 加强版吗？（需要找最大最小。）

实现

考虑 priority_queue 并不能找到最大最小并动态删除， 所以我们使用 multiset 代替。

multiset 是一种可以维护集合最大最小再删除的数据结构。

当然：你也可以使用平衡树等数据结构。

代码

超短黑题。

#include<bits/stdc++.h>
using namespace std;
int X,Y,Z;multiset<string> s;
int main(){
    scanf("%d%d%d",&X,&Y,&Z);
    for(int i=1;i<=X;++i) s.insert("a");
    for(int i=1;i<=Y;++i) s.insert("b");
    for(int i=1;i<=Z;++i) s.insert("c");
    while(s.size()>1){
        string l=*s.begin(),r=*s.rbegin();
        s.erase(s.begin());s.erase(--s.end());
        s.insert(l+r);
    }
    cout<<*s.rbegin();
    return 0;
}

Accept!