问题描述
小明带着N元钱去买酱油。酱油10块钱一瓶,商家进行促销,每买3瓶送1瓶,或者每买5瓶送2瓶。请问小明最多可以得到多少瓶酱油。
输入格式
输入的第一行包含一个整数N,表示小明可用于买酱油的钱数。N是10的整数倍,N不超过300。
输出格式
输出一个整数,表示小明最多可以得到多少瓶酱油。
样例输入
40
样例输出
5
样例说明
把40元分成30元和10元,分别买3瓶和1瓶,其中3瓶送1瓶,共得到5瓶。
样例输入
80
样例输出
11
样例说明
把80元分成30元和50元,分别买3瓶和5瓶,其中3瓶送1瓶,5瓶送2瓶,共得到11瓶。
思路:这题是典型贪心算法的应用,首先计算出能买5送2的组数cnt5,把钱减去cnt5*50,然后计算买3送1的组数cnt3,然后把钱减去cnt3*30, 计算只买1瓶的个数cnt1,那么总瓶数为cnt5*7+cnt3*4+cnt1。
AC代码:
#include <iostream>
using namespace std;
int ans = 0,sum;
int cnt1 = 0,cnt3 = 0,cnt5 = 0;
int Find(int sum,int num)
{
int i = 0;
for(i = 0 ; i*num*10 <= sum ; i++);
return i-1;
}
int main()
{
while(cin>>sum){
cnt5 = Find(sum,5);
ans += cnt5*7;
sum -= cnt5*50;
cnt3 = Find(sum,3);
ans += cnt3*4;
sum -= cnt3*30;
cnt1 = Find(sum,1);
ans += cnt1;
cout<<ans<<endl;
}
return 0;
}