Shock Wave

题目描述

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]$ 内的整数，那么它会对所有编号为 $i$（$i$ 为 $[0,N-1]$ 内整数）的瓷砖 $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$ 个测试用例的答案。

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

2
3
2
4
4
2000000000000000000

提示

对于第一个测试，用两次击打打碎所有瓷砖的唯一方法是对 $0$ 号瓷砖击打两次，从而分别施加总力量 $[0,2,4,6,8]$。 对于第二个测试，Bessie 用三次击打打碎所有瓷砖的一种方法是分别对 $0$、$2$ 和 $4$ 号瓷砖各击打一次，从而分别施加总力量 $[6,5,4,5,6]$。 对于第三个测试，Bessie 用两次击打打碎所有瓷砖的一种方法是分别对 $0$ 和 $1$ 号瓷砖各击打一次，从而分别施加总力量 $[1,1,3,5,7]$。 计分： 输入 2：所有 $p_i$ 都相等。 输入 3-6：$N\le 100$ 输入 7-14：无额外限制。 题目贡献：Suhas Nagar

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum