A70055 | $小午和小枫在河边捡了 $n$ 堆的石子，每堆石子有 $a_i$ 个石子$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

小午和小枫在河边捡了 $n$ 堆的石子，每堆石子有 $a_i$ 个石子。 现在他们想把这 $n$ 堆石子合并成一堆石子，由于他们的力量有限，每次只能从某一堆中最多只能将 $k$ 个石子搬到相邻的一堆中去。形式化地，每次操作他们可以将第 $i$ 堆中至多 $k$ 个石子搬运到第 $i-1$ 或 $i+1$ 堆。 请问他们最少需要搬几次才能将所有石子合并到一起。

第一行输入两个正整数 $n,k$ $(1\leq n\leq 2\times 10^5,1\leq k\leq 10^9)$ ，分别表示石子堆数和每次可以搬运的最多石子数量。 第二行输入 $n$ 个正整数 $a_i$ $(1\leq a_i\leq 10^9)$ ，表示第 $i$ 堆中石子的数量。

输出包含一个整数，表示将所有石子合并到一堆需要花费的最少搬运次数。

输入 #1

5 2
5 2 4 7 1

输出 #1

C++ 编辑器

输入

输出