题目描述
n 个班的小朋友乘大巴去郊游,第 i 个班有 ai 个人。
每隔一段时间就会来一辆空大巴车,每个大巴车可以容纳 m 个小朋友。
已知,在安排乘车时,必须按照 1 班,2 班,…,n 班的顺序,依次安排每个班的小朋友。
同一个班的小朋友必须被安排在同一辆车内。
也就是说,如果当前需要安排 i 班乘坐大巴,而此时大巴剩余的座位数量少于 ai,则让大巴先走,i 班以及后续班级共同等待下一辆大巴到来。
请问,将所有小朋友接走,共需多少辆大巴?
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,m。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果,表示所需大巴数量。
数据范围
1≤T≤30,
1≤n,m≤100,
1≤ai≤m
样例
输入样例:
2
4 3
2 3 2 1
3 4
1 2 1
输出样例:
3
1
解析
令一个x表示小朋友数目,将每个班的小朋友数目相加,当小朋友的数目大于m时,就能发车了所以ans,但这个时候由于x多加了一个a(表示每个班小朋友数)才会大于m,但是这个a坐的是下一趟车,所以令x等于这个a,再与后面的a相加。
由于到最后可能存在少于m的情况不能进行判断(就是最后不管剩下多少小朋友都需要一辆车,前提是要剩下),所以0<x<=m还要ans.
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int ans=0,x=0,a;
for(int i=1;i<=n;i++)
{
cin>>a;
x+=a;
if(x>m)
{
ans++;
x=a;
}
if(i==n&&0<x<=m)ans++;
}
cout<<ans<<endl;
}
return 0;
}