不翻题面 5.

· · 题解

考虑进行差分。
可以变成如下三种操作：

目标 \forall i \in [1, n], d_i=0。
首先考虑如果 \forall i \in [2, n], d_i=0，那么可以执行 |d_1| 次 2 或 3 操作。
于是我们就对于每一个 2 \sim n 的 i，都可以使用 1 或 2 操作（取决于 d_i 的符号）来转换到 d_1。将答案再加上 d_1 即可。
上伪代码（使用 \KaTeX 排版）：

\begin{array}{l} \textbf{input}~T \\ \textbf{for}~w=[1,T] \\ \qquad\textbf{input}~n,a_i \\ \qquad\textbf{for}~i=[1,n]\\ \qquad\qquad d_i\gets a_i-a_{i-1}\\ \qquad p \gets 0 \\ \qquad\textbf{for}~i=[2,n]\\ \qquad\qquad \textbf{if}~d_i<0 \\ \qquad\qquad\qquad p \overset-\gets a_i \\ \qquad\qquad\qquad a_1 \overset+\gets a_i \\ \qquad\qquad\textbf{else} \\ \qquad\qquad\qquad p \overset+\gets a_i \\ \qquad\textbf{output}~p+|a_1| \end{array}