[ZCMU OJ]5216: 买苹果(贪心+前缀和+细节+注意超时)

Description

小明遇到了一个难题，他现在只有 m 元钱，商场里有 n 个苹果每个苹果有对应的标价。现在，小明想要用 m 元钱买到尽可能多的苹果。

Input

第一行包含两个整数n,m，n 表示有 n 个苹果，m 表示小明有的钱。

第二行包含 n 个正整数，分别表示每个苹果的价格。

Output

输出一个整数表示小明最多能买几个苹果。

Sample Input

5 20 13 9 11 4 7

Sample Output

3

HINT

n≤105,m≤1018，所有苹果的价格不超过109

Source

[][][]

---------------------------------------------------------------------------------------------------------------------------------

这道题的思路简单来说是贪心，但是我写的前几个码出现了细节问题（情况考虑不完整）和超时的情况。

我创立了两个数组，第一个数组a存储苹果的价格，在sort排序之后，第二个数组b存储苹果价格的前缀和；即b[i]为买a中前i个苹果所花的价格。

（之前我只创立一个数组模拟从最小价格开始买苹果直到没钱继续买，就超时了）

4种情况（我考虑的）：

1.最便宜的苹果都买不起

2.钱只够买一个苹果

3.买不完所有苹果

4.可以买完所有苹果

ac代码↓

#include<bits/stdc++.h>
using namespace std;
long long a[100010],b[100010];
int main()
{
	long long n,m,i,k=0;
	
	scanf("%lld %lld",&n,&m);//本题仅一组数据 
	
		memset(a,0,sizeof(a));//数组初始化 
		memset(b,0,sizeof(b));
		
		for(i=0;i<n;i++)
		scanf("%lld",&a[i]);
		
		sort(a,a+n);//sort函数默认升序排列 
		
		if(a[0]==m)
		{
			printf("1\n");
			return 0;
		}
		else if(a[0]>m)
		{
			printf("0\n");
			return 0;
		}
		
		b[0]=a[0];
		
		for(i=1;i<n;i++)
		{
			b[i]=b[i-1]+a[i];//b数组存储a数组的前缀和 
			if(b[i]==m||b[i]<m&&i==n-1) //钱刚好够买或者可以买所有苹果 
			{
				printf("%lld\n",i+1);
				break;
			}
			else if(b[i]>m)//不能买所有苹果的情况 
			{
				printf("%lld\n",i);
				break;
			}
		}
	return 0;
}