2020第十一届蓝桥杯国赛-G游园安排

题面

【问题描述】

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 L 星球 游乐园的管理员。

为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系 统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟 0 个或多个小写英文字母。游客可能重名。

小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。

一个名字 A 小于另一个名字 B 是指：存在一个整数 i，使得 A 的前 i 个字 母与 B 的前 i 个字母相同，且 A 的第 i + 1 个字母小于 B 的第 i+ 1 个字母。（如 果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母，也视为 A 的第 i + 1 个字 母小于 B 的第 i + 1 个字母）

作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

【输入格式】

输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

【输出格式】

按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。

【样例输入】

WoAiLanQiaoBei

【样例输出】

AiLanQiao

【评测用例规模与约定】

对于 20% 的评测数据，输入的总长度不超过 20 个字母。

对于 50% 的评测数据，输入的总长度不超过 300 个字母。

对于 70% 的评测数据，输入的总长度不超过 10000 个字母。

对于所有评测数据，每个名字的长度不超过 10 个字母，输入的总长度不超 过 1000000 个字母。

思路

动态规划，最长上升子序列

• 已通过所有样例，供参考

考察最长上升子序列（LIS）。等价与每个游客的名字都是一个整数值（相同的名字值也相同），找到这些值构成的序列的最长上升子序列输出即可，且保证当有多个最长上升序列的情况下，输出值较小字典序的序列。

先将读入的名字拆分，之后按照最长上升子序的算法去做。

注意，本题不可以使用简单的动态规划，最坏情况下有$10^6$个游客需要进行处理，而动态规划的复杂度为$O(n^2)$，会TLE。

本题应该使用$O(n \times logn)$的二分结合动态规划做法来完成，可参见 最长上升子序列(LIS)长度的O(nlogn)算法。

用 b[i] 表示长度为 i 的最长上升子序列的最小结尾值，对原序列 a 进行遍历，当遇到当前字符串比 b 序列的最后一个值大，则扩展其到 b 的末尾，b 的长度+1；若小，则在 b 序列中二分查找到第一个比该字符串大的位置，替换该位置的值。

在上述过程中，用一个位置数组 pos 记录每次 a 数组的每个元素在 b 数组中的下标位置，用于后面反向推导出字典序最小的结果。

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;
char s[N];
string a[N], b[N];
int cnt, len, pos[N], ans[N];

int main() {
    scanf("%s", s);
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (isupper(s[i])) a[++cnt].push_back(s[i]);
        else a[cnt].push_back(s[i]);
    }

    len = 1;
    b[1] = a[1];
    pos[1] = 1; //保存 a[i] 在 b 中的下标位置
    for (int i = 2; i <= cnt; i++) {
        if (a[i] > b[len]) {
            b[++len] = a[i];
            pos[i] = len;
        } else {
            int k = lower_bound(b + 1, b + len + 1, a[i]) - b;
            b[k] = a[i];
            pos[i] = k;
        }
    }

    string maxv = "Zzzzzzzzzzz";
    int j = len;
    for (int i = cnt; i >= 1; i--) {
        if (!j) break;
        if (pos[i] == j && maxv > a[i]) {
            ans[j--] = i;
            maxv = a[i];
        }
    }

    for (int i = 1; i <= len; i++) cout << a[ans[i]];
    puts("");

    return 0;
}