时间限制:2 秒,空间限制:512 MB。
题目描述
长度为 n 的街道被积雪覆盖,将街道划分为 n 段,第 i 段的积雪量为 ai,保证 0≤ai≤m 且 ai 为整数。
天依与言和要来清理积雪,每次清理有 2 种选择:
- 天依从位置 1 走到位置 x,将积雪清理掉 c,再走回位置 1。同时,因为在雪地上移动,位置 1∼x 的积雪量减少 1,即 ∀i∈[1,x−1],ai:=ai−1,ax:=ax−c−1。
- 言和从位置 n 走到位置 x,将积雪清理掉 c,再走回位置 n。同时,因为在雪地上移动,位置 x∼n 的积雪量减少 1,即 ∀i∈[x+1,n],ai:=ai−1,ax:=ax−c−1。
任意时刻,积雪量对 0 取 max。
天依与言和想知道,最少进行多少次清理后(即最小化两人清理次数总和),能将所有积雪清除,即 \forall i \in [1, n], a_i = 0。
输入格式
本题有多组测试数据。
首先输入一行两个数 T, tid,T 表示数据组数,tid 表示子任务编号(样例的子任务编号为 0)。
对于每组数据:
第一行三个整数 n, m, c。
第二行 n 个整数 a_1 \sim a_n。
输出格式
对于每组数据,输出一行一个整数表示答案。
测试样例
样例输入 1
1 0 5 5 1 1 3 2 3 1
样例输出 1
2
样例解释 1
天依走到位置 4 清理,积雪量变为 [0, 2, 1, 1, 1]。
言和走到位置 2 清理,积雪量变为 [0, 0, 0, 0, 0]。
共 2 次清理。
样例 2
见附加文件中的 snow.in
与 snow.ans
。这个样例中有 100 组 n = 10, m = 10 的数据。
数据范围
对于 100\% 的数据,1 \le T \le 10^5,1 \le n, m \le 5 \times 10^5,\sum n, \sum m \le 10^6,0 \le a_i \le m,0 \le c \le 5 \times 10^5。
子任务编号 | n | m | 特殊限制 | 分值 | 子任务依赖 |
---|---|---|---|---|---|
1 | \le 5 \times 10^5 | \leq 5 \times 10^5 | c = 0 | 2 | |
2 | \leq 2 | 无 | 3 | ||
3 | \leq 5 | \leq 5 | T \le 10^5 | 4 | |
4 | \leq 50 | \leq 50 | \sum n, \sum m \le 200 | 10 | 3 |
5 | \leq 300 | \leq 300 | \sum n, \sum m \le 600 | 10 | 4 |
6 | \leq 2\,000 | \leq 2\,000 | \sum n, \sum m \le 4000 | 10 | 5 |
7 | \leq 5 \times 10^4 | \leq 5 \times 10^4 | c \le 20, \sum n, \sum m \le 10^5 | 20 | |
8 | \sum n, \sum m \le 10^5 | 15 | 6, 7 | ||
9 | \leq 5 \times 10^5 | \leq 5 \times 10^5 | c \le 20 | 10 | 1, 7 |
10 | 无 | 15 | 2, 8, 9 |