You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
42 lines
1.2 KiB
42 lines
1.2 KiB
/*
|
|
小米共有m个箱子用于打包行李，每个箱子承重为w。现有n件行李排成一行，重量为ai，
|
|
小米将从左向右开始打包。如果当前箱子装入该行李不会超重则优先装在当前箱子，
|
|
如果会超重则将当前箱子密封，将该行李装入下一个新的箱子中。小米更偏爱放在右边的行李，
|
|
所以为了能装入更多行李，他会选择从最左边开始连续地舍弃一些行李，以保证剩下的行李可以全部装完。
|
|
现在想知道，他最多可以装入多少件行李?
|
|
|
|
输入：
|
|
5 2 8
|
|
6 3 2 5 3
|
|
|
|
输出：
|
|
4
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
int main(){
|
|
int n, m;
|
|
long long w;
|
|
scanf("%d %d %lld",&n,&m, &w);
|
|
long long weights[n];
|
|
for(int i=0;i<n; ++i)scanf("%lld",&weights[i]);
|
|
int boxcount =1;
|
|
long long currentweight =0;
|
|
int rightIndex=n-1;
|
|
while(rightIndex>=0){
|
|
if(currentweight + weights[rightIndex]<=w){
|
|
currentweight += weights[rightIndex];
|
|
} else {
|
|
boxcount++;
|
|
currentweight = weights[rightIndex];
|
|
}
|
|
rightIndex--;
|
|
if(boxcount>m){
|
|
rightIndex++;
|
|
break;
|
|
}
|
|
}
|
|
int itemsPacked=n - (rightIndex + 1);
|
|
printf("%d\n",itemsPacked);
|
|
return 0;
|
|
}
|