← 返回题目列表

Codeforces · 2134/C

C. 更大

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

调用一个数组 好 如果对于每个长度至少为 $$$2$$$ 的子数组$$$^{\text{∗}}$$$,偶数索引处的元素之和(相对于 原始数组) 大于或等于奇数索引处的元素之和。数组索引从$$$1$$$开始。

例如,数组 $$$[3,8,4,4]$$$ 和 $$$[2,3,1,4,2]$$$ 就很好。数组$$$[0,2,4,1]$$$不是,因为在子数组$$$[2,4,1]$$$中,原始数组中偶数索引处的元素是$$$2$$$(索引$$$2$$$)和$$$1$$$(索引$$$4$$$),而奇数索引处的唯一元素是$$$4$$$(索引$$$3$$$)。由于 $$$2 + 1 \lt 4$$$,条件确实 不 保留该子数组。

给你一个 $$$n$$$ 数组 非负 整数 $$$a_1,a_2,\ldots,a_n$$$。在一次操作中,您可以将数组中的任何元素减少 $$$1$$$,但所有元素必须保留 非负。您的任务是找到使数组 $$$a$$$ 良好所需的最少操作数。可以证明,使用有限次数的操作可以使数组变得良好。

$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

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

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

输出

对于每个测试用例,在新行中输出一个整数 - 使数组 $$$a$$$ 良好所需的最少操作数。

示例

输入
复制

8
4
3 8 4 4
4
0 2 3 5
2
3 1
5
2 3 1 4 2
4
0 2 4 1
5
3 1 4 5 1
11
3 0 5 4 4 5 3 0 3 4 1
12
410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354 801228787 44181004 1000000000 3829103

输出
复制

0
1
2
0
3
6
14
4450984776

注意

在第一个测试用例中,数组 $$$a$$$ 已经很好,所以答案是 $$$0$$$。以下是每个子数组的检查:

子数组偶数索引总和奇数索引和满足条件吗?
$$$[3,8]$$$$$$8$$$$$$3$$$是
$$$[8,4]$$$$$$8$$$$$$4$$$是
$$$[4,4]$$$$$$4$$$$$$4$$$是
$$$[3,8,4]$$$$$$8$$$$$$3+4=7$$$是
$$$[8,4,4]$$$$$$8+4 = 12$$$$$$4$$$是
$$$[3,8,4,4]$$$$$$8+4=12$$$$$$3 + 4 = 7$$$是

在第二个测试用例中,数组 $$$a$$$ 不好:

子数组偶数索引总和奇数索引和满足条件吗?
$$$[0,2]$$$$$$2$$$$$$0$$$是
$$$[2,3]$$$$$$2$$$$$$3$$$No
$$$[3,5]$$$$$$5$$$$$$3$$$是
$$$[0,2,3]$$$$$$2$$$$$$0+3=3$$$No
$$$[2,3,5]$$$$$$2 + 5 = 7$$$$$$3$$$是
$$$[0,2,3,5]$$$$$$2+5 = 7$$$$$$0+3 = 3$$$是

但是,如果我们对索引 $$$3$$$ 执行操作,数组将变为 $$$[0,2,2,5]$$$ 并且现在就可以了:

子数组偶数索引总和奇数索引和满足条件吗?
$$$[0,2]$$$$$$2$$$$$$0$$$是
$$$[2,2]$$$$$$2$$$$$$2$$$是
$$$[2,5]$$$$$$5$$$$$$2$$$是
$$$[0,2,2]$$$$$$2$$$$$$0+2=2$$$是
$$$[2,2,5]$$$$$$2 + 5 = 7$$$$$$2$$$是
$$$[0,2,2,5]$$$$$$2+5 = 7$$$$$$0+2 = 2$$$是

因此,答案是$$$1$$$。