A6138. 「USACO 2025.1 Platinum」Shock Wave
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [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$ 的力量。
请求出击破所有砖块所需要的最少击打次数。
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$。
第 $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