显然每次装重量最小的苹果是最优的。
代码如下(c++)
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int m, n,sum=0;
cin >> m >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n, less<int>());
for (int i = 0; i < n; i++) {
if (sum + arr[i] > m) {
cout << i << endl;
return 0;
}
else {
sum += arr[i];
}
}
cout << n << endl;
return 0;
}
(c)
#include<stdio.h>
#include<stdlib.h>
int main(){
int m,n,sum=0;
scanf("%d %d",&m,&n);
int *arr=(int *)malloc(n*sizeof(int));
for (int i=0;i<n;i++) scanf("%d",arr+i);
for (int i=0;i<n-1;i++){
for (int j=0;j<n-1-i;j++){
if (arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for (int i=0;i<n;i++){
if (sum+arr[i]>m){
printf("%d\n",i);
return 0;
}else {
sum+=arr[i];
}
}
printf("%d\n",n);
return 0;
}