ZROI P2578 题解

题面

点击此处展开题面

爱新撅罗

小 X 穿越了，发现自己成为了一个小人，正准备为一位清朝王爷服务。只要好好地服务，王爷就有赏。

一开始，小X的赏赐是 $a_0$，满足 $0 \leq a0 \leq 9$。

小 X 将为王爷服务 $n$ 次，第 $i$ 次他有两种方式为王爷服务：

• 为王爷整理胡子。 王爷会在原有赏赐的数字左侧添加一位，添加的数字为 $a_i (0 \leq ai \leq 9)$。
• 给王爷唱歌。 王爷会在原有赏赐的数字右侧添加一位，添加的数字为 $a_i$。

小X想知道，他最终能获得的最多赏赐是多少。

输入格式

第一行一个整数 $n$，表示服务的次数。

第二行 $n + 1$ 个 0 到 9 的整数，表示 $a_0, a_1, a_2, \ldots, a_n$。

保证 $a$ 中不全为 0。

输出格式

一个数，表示小 X 取得的最多赏赐。

样例

input

6
0 1 2 3 2 6 4

output

6321024

样例解释

$a_1$ 到 $a_6$ 的放置顺序：左左左右左右。

数据范围

对于 30% 的数据，$n \leq 18$。

对于 50% 的数据，$n \leq 3000$。

对于另外 10% 的数据，$a$ 中含有恰好两种数，即存在 $x \neq y$，使得对于任意 $i$，$a_i = x$ 或 $a_i = y$。

对于 100% 的数据，$n \leq 106$。

解题

考虑 $\overline{xyz}$ 要在头或尾接上 $a$：

• 如果接在头：

  $$\overline{axyz} = 1000a + 100x + 10y + z \tag{1}$$

• 如果接在尾：

  $$\overline{xyza} = 1000x + 100y + 10z + a \tag{2}$$

$(1) - (2)$ 得 $999a-900x-90y-9z$，所以当 $111a > 100x + 10y + z$ 时 $(1) > (2)$，即当 $\overline{aaa} > \overline{xyz}$ 时应接在头。

由于每一步都应是最优解，所以 $\overline{xyz}$ 中 $\overline{xx} > \overline{yz}$ ，又有 $y > z$，所以 $x \geq y$，所以 $a \geq x$。

推广可得：如果当前数字 $\geq$ 已有数字的最高位，那么应接在头，否则应接在尾。

考虑到要在头尾接上，可以使用双向列表实现。

代码

#include <iostream>
#include <queue>
using namespace std;

const int N = 1e6 + 5;
int a[N], maxs[N];
deque<char> ans;

int main() {
  int n;
  scanf("%d", &n);
  // @attention 输入输出全部从 0 到 n
  for (int i = 0; i <= n; ++i) scanf("%d", &a[i]);
  ans.push_back(a[0]);
  for (int i = 1; i <= n; ++i) {
    // 答案的第一位一定是当前最大的，
    // 所以`a[i]` 只要不小于当前答案第一位，就是 `a[0...i]` 中最大的
    if (a[i] >= ans.front())
      ans.push_front(a[i]);
    else
      ans.push_back(a[i]);
  }
  for (int i = 0; i <= n; ++i) {
    printf("%d", ans.front());
    ans.pop_front();
  }
  return 0;
}