AT3577题解

· · 题解

AT_code_festival_2017_qualb_f (原 AT3577) Largest Smallest Cyclic Shift

题目传送门

哎呀！这道题黑也真不可思议！（请忽略我的这句话）

思路

首先，我们可以先构造一个排序数组，一开始里面有 X 个 a，Y 个 b，Z 个 c。重点！ 我们知道，现在处于最前面的那个字符（串）会是 f(T) 的前缀。既然是最小了，不能再小了，所以我们就要让他的后面跟着的东西尽量大，这样才小得不亏！这就是 贪心的策略。

实现

定义一个“排序数组”，里面存入 X 个 a，Y 个 b，Z 个 c，然后每一次把最前面的和最后面的字符（串）删掉，把它们连起来加到这个“排序数组”里面。

如何用代码实现呢？

大家肯定都知道 priority_queue，但是 priority_queue 删除最后一项，我暂时没找到快速的方法。然后我上网找了一下，找到了这个东西：multiset，它既能像 set 一样排序，也可以保留多个同样的元素。

比如说：

set<int> s;
s.insert(1);
s.insert(1);
cout << s.size() << endl;

会输出 1。

而

multiset<int> s;
s.insert(1);
s.insert(1);
cout << s.size() << endl;

会输出 2。

还有一点，multiset 也在头文件 set 里。 最后就上代码了！

AC Code

#include <iostream>
#include <set>
#include <string>
using namespace std;

inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x * 10) + (ch ^ '0');
        ch = getchar();
    }
    return x;
}

int main()
{
    multiset<string> s;
    int X, Y, Z;
    X = read();
    Y = read();
    Z = read();
    while (X--)
    {
        s.insert("a");
    }
    while (Y--)
    {
        s.insert("b");
    }
    while (Z--)
    {
        s.insert("c");
    }
    string l, r;
    while (s.size() > 1)
    {
        // 其实这里也可以换一个做法。
        l = *s.begin();
        r = *s.rbegin();
        s.erase(s.lower_bound(l)); // 不会到了2202年还有人不知道lower_bound吧！
        s.erase(s.lower_bound(r));
        s.insert(l + r);
    }
    cout << *s.begin() << endl;
    return 0;
}

AC Record

望题解过审！