题意
一共有n组人(小于等于巴士容量),每一车能拉走m个人。
一次性可以拉好几组人,但一次必须带一整组人,不可以改变组之间的顺序。
求最后用的巴士数量。
题解
直接膜你贪心,记录等这班车的人数。
对于每组人,如果能带走就带走,带不走就让他们等下一班巴士。
具体详情见代码注释。
代码
#include<stdio.h>
int n,m,a,wait,res; //wait表示当前等着走的人数
int main()
{
scanf("%d%d",&n,&m);
while(n--) //输入每组人数
{
scanf("%d",&a);
if(a+wait<=m) wait+=a; //如果巴士能够带走这组人数加上之前等着走的人数,就让这组也加入等的行列
else //如果无法全部带走
{
++res; //多用一辆巴士
wait=a; //带走之前等的人(wait=0),然后让这组人等(wait=a)
}
}
if(wait) ++res; //注意特判是否还剩下人
printf("%d\n",res);
return 0;
}