← 返回题目列表

Codeforces · 1534/B

B. 直方图丑陋

中文机器翻译题面 查看原题

小多米在圣诞节收到了一张直方图,其中包含 $$$n$$$ 条形,高度为 $$$a_1、a_2、\ldots、a_n$$$。然而,他对新直方图玩得越多,就越意识到它的缺陷,所以今天他想根据自己的喜好修改它。

要修改直方图,Little Dormi 可以执行任意次数的以下操作:

- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$),其中 $$$a_i>0$$$,并分配 $$$a_i := a_i-1$$$。

Little Dormi 将他的直方图(执行一定次数的操作后)的丑陋分数定义为其轮廓的垂直长度与他对其执行的操作次数之和。为了使直方图尽可能完美,他希望通过一些操作修改后将丑陋分数最小化。

然而,由于他的直方图非常大,Little Dormi 很难最小化丑陋分数,所以作为 Little Dormi 的哥哥,帮助他找到最小的丑陋分数。

考虑以下示例,其中直方图具有高度为 $$$4,8,9,6$$$ 的 $$$4$$$ 列:

蓝色区域代表直方图,红线代表轮廓的垂直部分。目前,轮廓的垂直长度为$$$4+4+1+3+6 = 18$$$,所以如果Little Dormi根本不修改直方图,丑陋的程度将是$$$18$$$。

但是,Little Dormi 可以在 $$$2$$$ 列上应用一次操作,在 $$$3$$$ 列上应用两次操作,从而得到高度为 $$$4,7,7,6$$$ 的直方图:

现在,由于轮廓(红线)的总垂直长度为 $$$4+3+1+6=14$$$,因此丑陋程度为 $$$14+3=17$$$ 美元。可以证明这是最优的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个输出一个整数的测试用例,Little Dormi 通过该测试用例中的直方图可以实现的最小丑陋。

示例

输入 #1

2
4
4 8 9 6
6
2 1 7 4 0 0

输出 #1

17
12

注意

示例 $$$1$$$ 是语句中描述的示例。

例如 $$$2$$$ 的初始直方图如下:

目前的丑陋程度为$$$2+1+6+3+4=16$$$。

通过对 $$$1$$$ 列应用一次操作,对 $$$3$$$ 列应用操作六次,对 $$$4$$$ 列应用操作三次,我们最终可以得到高度为 $$$1,1,1,1,0,0$$$ 的直方图:

现在轮廓的垂直长度为$$$1+1=2$$$,小多米进行了$$$1+6+3=10$$$操作,所以最终的丑数为$$$2+10=12$$$,可以证明是最优的。