牛客网——买苹果（水题贪心）

84 阅读 0 评论 56 点赞

我是靠谱客的博主懵懂小伙，这篇文章主要介绍牛客网——买苹果（水题贪心），现在分享给大家，希望可以做个参考。

点击打开链接

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

输入描述:

复制代码

1
输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述:

复制代码

1
输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

示例1

输入

复制

复制代码

1
20

输出

复制

复制代码

1
3

题意：n个苹果，有6个一袋，8个一袋的，最少需要买多少袋的。如不能买输出-1.

解题思路：因为求的是最少袋数，且数据量很小，可以从8开始枚举。（1）可以被8整除（2）8x+6y=n，从12到1开始枚举8（3）可以被6整除的。前后顺序不能变，因为是求最少袋数，所以以贪心的思想，先拿多的，不够再拿少的。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cmath>
using namespace std;
long long a[1000009];
int main()
{
int n;
while(cin>>n)
{
int flag=0;
if(n%8==0)
{
cout<<n/8;
continue;
}
for(int i=12;i>=1;i--)
{
if(n>=8*i&&(n-8*i)%6==0)
{
flag=1;
cout<<i+(n-8*i)/6<<endl;
break;
}
}
if(!flag && n%6==0)
{
cout<<n/6;
continue;
}
if(!flag)
{
cout<<"-1"<<endl;
}
}
return 0;
}