Skip to content

11628: 【原1628】Interesting Truck

题目

题目描述

author: xzj 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1628

Description

xzj爱吃糖。 给定很多堆糖果,每一堆糖果有a[i]个,按顺序摆在地上。 xzj开着卡车来运糖果,很不幸卡车的运载量有个固定的上限T,每次xzj不能运送超过T个糖果。 运输糖果有如下要求:

  1. 不能把一堆糖果拆开分多次运输;
  2. 当一堆糖果左右两侧的糖果堆尚未被运走时,这一堆也不能被运走。(即每次运输选择一个前缀+一个后缀,前缀和+后缀和<=T)

请聪明的你帮帮xzj,告诉他最少几次才能运走全部的糖果呢?

Input Format

第1行两个整数 N,T。

第2行N个整数a[i],即为该糖果数列。

Output Format

一个输出,代表最少运送次数。

Sample Input

7 10
7 7 7 1 1 6 1

Sample Output

4

Limits

对于30%的数据,n不超过10; 对于60%的数据,n不超过100; 对于80%的数据,n不超过1000; 对于100%的数据,n不超过8000.

(对于所有的数据,保证0<=a[i]<=T,T<=10^8)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!