『STA - R2』Locked - Luogu - 题目详情

ID: 8436

远端评测题

1000ms

512MiB

难度: 3

上传者:

标签>

O2优化

题目背景

GOD_hj 有一把数字密码锁，但是他陷于 whk，没时间来开锁。

这把锁从左到右有 $n$ 个数，组成了一个序列 $\{a\}$ 。

由于 GOD_hj 的记性不好，所以只要将锁设置为输入任意单峰序列即可打开。具体为：

a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n)

GOD_hj 的锁是拨动式的，即拨一下就能换成临近的一个数（ $0$ 和 $9$ 可以互换）。

求最少拨几下可以开锁。

第一行一个整数， $n$ 。

第二行 $n$ 个整数，为序列 $\{a\}$ 。

一个整数，为最少要拨动几下。

3
1 2 3

7
1 2 6 5 6 7 2

【样例解释】

样例二：把第四个 $5$ 变为 $6$ 或把第三个 $6$ 变为 $5$ 。

【数据范围】

本题采用捆绑测试。

\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm n\le &\textbf{分值}&\textbf{特殊性质} \\\hline \textsf{1} & 5 & 5 & \textbf{无} \\\hline \textsf{2} & 10^3 & 25 & \textbf{无} \\\hline \textsf{3} & 5\times 10^5 & 20 & \textbf{无} \\\hline \textsf{4} & 5\times 10^6 & 10 & a_i\in\{0,1\} \\\hline \textsf{5} & 5\times 10^6 & 40 & \textbf{无} \\\hline\hline \end{array}

对于全部数据， $1\le n\le 5\times 10^6$ ， $0\le a_i<10$ 。

Upd on 2023/06/12：新加 5 组 Hack 数据，放入 Subtask 6，不计分。