AT4116 [ABC095B] Bitter Alchemy 题解

题意简述


糕点师会做 nn 种不同的蛋糕,给出制作每个蛋糕的面粉的质量 aia_i

现在题目又给出整数 mm,指现在有 mm 克面粉(显然 aa 序列的所有单位都为克)

求这位糕点师在做所有它会做的蛋糕的前提下,最多能做多少个蛋糕。

解题思路


显然的贪心。

先做所有自己会做的,然后选择质量最小的那种做,知道面粉不够这种蛋糕在做为止。

可以证明,这种方法是最优解。

代码实现


#include<bits/stdc++.h>
using namespace std;
int n,x,sum,tmp,minn=INT_MAX;
int main() {
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++) {
		scanf("%d",&tmp);
		sum+=tmp; minn=min(minn,tmp);
	}
	printf("%d",(x-sum)/minn+n);
	return 0;
}
//code by TheCedar