Cyclic Array

题目描述

给出一个由 n 个值构成的环状数组。每个元素有两个相邻元素；位置 n 和 1 的元素也被视为相邻。\n你的任务是将数组划分成若干子数组，使得每个子数组的和至多为 k。最少需要多少个子数组？

输入格式

第一行输入包含整数 n 和 k。\n下一行有 n 个整数 $x_1,x_2,\ldots,x_n$：数组的内容。\n总是存在至少一种划分（即数组中没有大于 k 的值）。

输出格式

输出一个整数：最少的子数组数量。

8 5
2 2 2 1 3 1 2 1

3

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ $1 \le k \le 10^{18}$ 样例解释：我们可以构造三个子数组：$[2,2,1]$，$[3,1]$，和 $[2,1,2]$（记住数组是环状的）。

标签: CSES1191|附加题1

来源

CSES1191|附加题1