所有工位的零件数均为正数,因此可以用滑动窗口维护当前连续区间的零件和。
每个元素最多被左右指针各访问一次,整体线性。
一条传送带上依次排列着 n 个工位,第 i 个工位堆放了 wi 件零件。你需要选取一段连续工位 [L,R](1≤L≤R≤n),一次性取走这段上的全部零件。手推车的容量为 c,因此取走的零件总数不能超过 c,即 ∑i=LRwi≤c。
请计算合法区间的最大长度 R−L+1。若不存在任何合法区间,则输出 0。
数据范围:工位个数 n 满足 1≤n≤2×105;容量 c 满足 1≤c≤1012;每个工位的零件数满足 1≤wi≤109。
第一行包含两个整数 n 和 c(1≤n≤2×105,1≤c≤1012),分别表示工位个数与手推车容量。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册