[编程题]买苹果
- 热度指数：29063 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。
输入描述:
输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果
输出描述:
输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1
示例1
输入
20
输出
3
每袋苹果相差是2个。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
// 最多的袋数
int n = (int)Math.ceil((double)a / 8);
boolean flag = false;
for(int i = n; i >= 0; i--) {
// 每有一袋6个，就少2个
if((8*n - 2*i) == a){
flag = true;
System.out.println(n);
break;
}
}
if(!flag){
System.out.println(-1);
}
// int b = in.nextInt();
// System.out.println(a + b);
}
}
}
发表于 2024-11-25 15:54:34
回复(0)
贪心，6和8最小公倍数是24，因此买的苹果中每24个苹果，一定会选择3袋装，而不会选择4袋装，不满24个的部分，穷举一下所有可能。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int res = 0;
res = (n / 24) * 3;
Map<Integer, Integer> map = new HashMap<>();
map.put(6,1);
map.put(12,2);
map.put(18,3);
map.put(8,1);
map.put(16,2);
map.put(14,2);
map.put(20,3);
map.put(22,3);
int rest = n % 24;
if(rest == 0)
res += 0;
else if(map.containsKey(rest)) {
res += map.get(rest);
} else res = -1;
System.out.println(res);
}
}
发表于 2020-06-15 15:55:23
回复(0)
Java实现，已通过。
思路：为了满足“想购买尽量少的袋数方便携带”。 先看能否被8整除，（ 为了保证袋数最少 ）不行的话，每次减14（6+8，两个袋子），再去整除8或6，袋子数也就是减14的次数*2+整除8或6的商。
如果减到负的了，说明每次减14（6+8）方案不可行，这时判断一下能否被6整除，（6个6个装也可成一种方案）不行的话就说明没有袋子方案。代码如下：
如果减到负的了，说明每次减14（6+8）方案不可行，这时判断一下能否被6整除，（6个6个装也可成一种方案）不行的话就说明没有袋子方案。代码如下：
import java.util.Scanner;
public class Main {
public static int howManyApple(int total)
{
int result=-1;
int time=1;
int temp=total;
if(total%8==0)
{ result=total/8;}
else
{while (total>0)
{
total=total-14;
if(total%8==0) {result=time*2+total/8;break;}
else if(total%6==0) {result=time*2+total/6;break;}
time++;
}
if(total<=0)
{if(temp%6==0) result=temp/6;}
}
return result;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
System.out.println(howManyApple(in.nextInt()));
}
}
发表于 2020-01-21 11:24:25
回复(0)
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int N = scan.nextInt();
int n=0;
int sum;
boolean flag = false;
int j = 0;
for (int i = 0; i < 4; i++) {
sum=n;
j=i;
while ( sum <= N ) {
if (sum==N) {
flag=true;
break;
}
j++;
sum+=8;
}
if (flag==true) {
break;
}
n+=6;
}
System.out.println(flag?j:-1);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int N = scan.nextInt();
int n=0;
int sum;
boolean flag = false;
int j = 0;
for (int i = 0; i < 4; i++) {
sum=n;
j=i;
while ( sum <= N ) {
if (sum==N) {
flag=true;
break;
}
j++;
sum+=8;
}
if (flag==true) {
break;
}
n+=6;
}
System.out.println(flag?j:-1);
}
}
发表于 2018-09-29 19:14:35
回复(0)
package test20180826;
import java.util.Scanner;
/*
感觉我这个思路蛮简单，首先是看可以对8整除不，
如果不能在看可以选出几个8和6组合，
8的个数从app/8到0个变化，取相应的6的个数。
如果上边取不到整数，就相当于不可行。
我前后使用了一个标记，boo,如果取到整数了
就是true，否则是false,
*/
public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
boolean boo = false;
while (sc.hasNext()) {
int app = sc.nextInt();
if (app % 8 == 0) {
System.out.println(app / 8);
boo = true;
} else {
for (int i = app / 8; i >= 0; i--) {
if ((app - i * 8) % 6 == 0) {
System.out.println(i + (app - i * 8) / 6);
boo = true;
break;
}
}
if (boo == false) {
System.out.println(-1);
}
}
}
}
}
编辑于 2018-08-26 10:48:45
回复(1)
import java.util.*;
public class Main {
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
if(n%8==0) {
System.out.println(n/8);
}
else if(n%8==4&&n/8>=2) {
System.out.println(n/8+1);
}
else if(n%8==2&&n/8>=2) {
System.out.println(n/8+1);
}
else if(n%6==0) {
System.out.println(n/6);
}
else {
System.out.println(-1);
}
}
}
发表于 2018-08-06 21:39:20
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
if(n<6||n%2!=0||n==10){
System.out.println(-1);
}
else if(n%8==0){
System.out.println(n/8);
}
else{
System.out.println(n/8+1);
}
}
}
发表于 2018-07-16 19:33:43
回复(0)
鸡兔同笼，先让8个一袋的数量最大，然后6个一袋的从0增，8个一袋从最大值减。 import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(bags(n));
}
public static int bags(int n) {
if (n < 6)return -1;
if (n == 7)return -1;
int a = n / 8;
int b = (n - a * 8)/ 6;
if (a * 8 + b * 6 == n) return a + b;
while (a >= 0 && b >= 0) {
if (a * 8 + b * 6 > n) {
a --;
}else if (a * 8 + b * 6 < n){
b ++;
}else {
return a + b;
}
}
return -1;
}
}
发表于 2018-05-24 23:41:46
回复(0)
import java.util.Scanner;
public class Main {
static int i;
static int j;
static int k=0;
int x;
static int sum=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int x=sc.nextInt();
for(i=0;i<18;i++){
for(j=0;j<14;j++){
if(6*i+8*j==x){
int o=i+j;
if(sum==0){
sum=o;
k++;
}else if(sum!=0){
if(sum>o){
sum=o;
}
}
}
}
}
if(k==0){
System.out.println("-1");
}else if(k!=0){
System.out.println(sum);
}
}
}
发表于 2018-03-18 23:27:49
回复(0)
如果当前数字不等于6i+8j,则返回-1.
如果可以的话，袋子数最小的时候为8个苹果袋子最多时
找到返回即可
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
for (int i = num / 8; i >= 0; i--) {
int temp = (num - (8*i)) % 6;
if (temp == 0){
System.out.println(i + (num - 8 * i)/6);
return;
}
}
System.out.println(-1);
}
}
发表于 2018-03-14 17:16:24
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double xx = n / 8.0;
int x = (int)xx;
if (xx == x){
System.out.println(x);
return;
}
for (int i=x; i>=0; i--){
if ((n - 8*i) % 6 == 0){
System.out.println((i + (n-8*i)/6));
return;
}
}
System.out.println(-1);
}提交观点
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double xx = n / 8.0;
int x = (int)xx;
if (xx == x){
System.out.println(x);
return;
}
for (int i=x; i>=0; i--){
if ((n - 8*i) % 6 == 0){
System.out.println((i + (n-8*i)/6));
return;
}
}
System.out.println(-1);
}提交观点
}
注意是 double xx = n / 8.0;
发表于 2018-03-03 12:31:59
回复(0)
//贪心的思维
/**
当不能被8整除时，那么便将苹果减6，count++；一旦可以被8整除时，那么就可以
直接输出；在这个过程中当苹果数小于6时，结束，不符合。
*/
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int num = in.nextInt();
int count = 0;
while (true) {
if (num < 6) break;
if (num % 8 == 0) {
count += num / 8;
num = 0; break;
} else {
num -= 6;
count++;
}
}
if (num > 0) System.out.println(-1);
else System.out.println(count);
}
}
}
-------------------------------------------------------------------------
//动态规划
/**
f(6) = f(8) = 1
f(i) = min(f(i-6) + 1, f(i-8) + 1);
*/
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int total = in.nextInt();
int[] array = new int[total + 1];
Arrays.fill(array, Integer.MAX_VALUE);
array[0] = 0;
for (int i = 0; i <= total; i++) {
if (array[i] != Integer.MAX_VALUE) {
if (i + 6 <= total) array[i + 6] = Math.min(array[i] + 1, array[i + 6]);
if (i + 8 <= total) array[i + 8] = Math.min(array[i] + 1, array[i + 8]);
}
}
int res = array[total] == Integer.MAX_VALUE? -1: array[total];
System.out.println(res);
}
}
}
编辑于 2017-12-08 20:11:21
回复(0)
这道题好简单，简直是小学数学啊，就按照解题思路编程就okimport java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int count = Integer.parseInt(scanner.nextLine()); LinkedList<Integer> result = new LinkedList<>(); int num6 = count / 6; int x; int y; for (x = 0; x <= num6; x++) { if ((count - (x * 6)) % 8 == 0) { y = (count - (x * 6)) / 8; result.add(x + y); } } if (result.size() == 0) { System.out.println(-1); } else { int min = result.get(0); for (int i = 0; i < result.size(); i++) { if (result.get(i) < min) { min = result.get(i); } } System.out.println(min); } } } }
发表于 2017-11-21 19:34:44
回复(0)
import java.util.*;
public class Main{
//买苹果
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int flag = 0 ;
while(scan.hasNext()){
int n = scan.nextInt();
lableA:
for(int x=0;x<17;x++){
for(int y=0;y<13;y++){
int t =6*x+8*y;
if(t==n) {
System.out.println(x+y);
flag = 1;
break lableA;
}
}
}
}
if(flag ==1){}else{
System.out.println(-1);
}
}
}
public class Main{
//买苹果
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int flag = 0 ;
while(scan.hasNext()){
int n = scan.nextInt();
lableA:
for(int x=0;x<17;x++){
for(int y=0;y<13;y++){
int t =6*x+8*y;
if(t==n) {
System.out.println(x+y);
flag = 1;
break lableA;
}
}
}
}
if(flag ==1){}else{
System.out.println(-1);
}
}
}
发表于 2017-10-27 00:27:22
回复(0)
public class Main{
//思路：我的解法比较简单，先找6和8的最小公倍数24，只要给定的n比24大，那么是24的倍数那一部分肯定都是
//用8个每袋的包装。剩余的不到24的那一部分其实就是解方程：n = 6*j + 8*i，其中n小于
//24,用两个for循环直接遍历出看有没有整数解即可。没有返回-1.
//时间复杂度：O(1)
public static int getPocketNumber(int n){
int res = 0;
int temp = n /24;
res = temp *3 ;
n %= 24;
boolean flag = false;
for (int i=2; !flag && i>=0; --i){
for (int j = 0; !flag && j<=2; ++j){
if((6 * j + 8*i) == n){
res += i+j;
flag = true;
}
}
}
if (flag){
return res;
}else {
return -1;
}
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int res = getPocketNumber(n);
System.out.println(res);
}
}
编辑于 2017-09-02 21:51:45
回复(0)
个人思路为：因为需要拿最少的，所以可以将总数除以8进行0，n/8遍历判断，然后将剩余的苹果数除以6进行判断是否能整除即可。
在牛客交流区里面看到大神直接复杂度=o(1)解出来，看了代码恍然大悟，原来本题目不在于结果，而在于你能否用最优的办法解，刚开始还以为是个**题，其实是在下**了。
确实，6和8很特殊，能组成10以外任何偶数，而对于奇数，是绝对不可能恰好恰好够完的，受教了。
还是贴上本人的代码，供像我一样的菜鸟参考
import java.util.Scanner;
public class StringUtil {
//买苹果之捆绑交易
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int temp = n;
for(int i=n/8; i>=0; i--){
temp = n-8*i;
if(temp%6 == 0){
System.out.println(i+temp/6);
return;
}
}
System.out.println(-1);
}
}
发表于 2017-08-31 14:31:37
回复(0)
//复杂度O(1)方法
import java.util.*;
public class Main{
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int n = in.nextInt();
System.out.println(count(n));
}
}
public static int count(int n){
if(n%2!=0||n==10||n<6) return -1;//一定是偶数（6，8都是）,最小是6，10以上偶数都可以；
if(n%8==0) return n/8;//如果拿八个拿完最好
return 1+n/8;//对于10以上的偶数，只要对8取余数不为0，就要从前面的1或者2个8中拿出2个，把余数补为6（本来余数就是6，就不用拿）。所以+1；
}
}
编辑于 2016-09-13 19:05:28
回复(33)
问题信息
通过挑战的用户
查看代码-
2023-03-10 15:57:21
-
2023-03-10 02:28:22
-
2023-02-09 16:42:18
-
2023-02-02 12:55:40 -
2022-12-25 00:44:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
