A6138 | $「USACO 2025.1 Platinum」Shock Wave$

时间限制2s

内存限制256MB

通过 / 提交0/0

题目描述

**题目来自 [USACO 2025 January Contest, Platinum](https://usaco.org/index.php?page=jan25results) Problem 2. [Shock Wave](https://usaco.org/index.php?page=viewproblem2&cpid=1477)** Bessie 正在试验一种能够产生巨大冲击波的强大的蹄部植入物。她有 $N$（$2 \leq N \leq 10^5$）块砖块排开在面前，分别需要至少 $p_0,p_1,\dots,p_{N-1}$ 的力量才能击破（$0 \leq p_i \leq 10^{18}$）。 Bessie 可以通过击打特定的砖块来施加力量，但由于她的植入物的奇特性质，它不会对她所击打的那块砖块施加任何力量。相反，如果她选择击打砖块 $x$ 一次，其中 $x$ 是一个 $[0,N-1]$ 范围内的整数，对所有在 $[0,N-1]$ 范围内的整数 $i$，它将对砖块 $i$ 施加 $|i-x|$ 的力量。同时这个力量是累积的，因此对一块砖块施加两次 $2$ 的力量将对该砖块施加总共 $4$ 的力量。 请求出击破所有砖块所需要的最少击打次数。

输入的第一行包含 $T$（$1 \leq T \leq 100$），为测试用例的数量。 第 $2t$ 行包含一个整数 $N$，为测试用例 $t$ 中的砖块数量。 第 $2t+1$ 行包含 $N$ 个空格分隔的整数 $p_0,p_1, \ldots, p_{N-1}$，表示砖块 $i$ 需要 $p_i$ 的力量才能击破。 输入保证一个测试点中的所有 $N$ 之和不超过 $5\cdot 10^5$。

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。

输入 #1

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

输出 #1

2
3
2
4
4
2000000000000000000

C++ 编辑器

输入

输出