笔试题-最少的袋子数装苹果

2022-6-22 diaba 笔试题 

package com.jiucaiyuan.net.question;

/**
 * 【问题】小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装，
 * 包装不可拆分。可是小虎只想购买恰好n个苹果，小虎想够买尽量少的袋数方便携带。如果不能购买
 * 恰好n个苹果，小虎将不会购买，输入一个整数n，表示小虎想购买的苹果个数，返回最小使用多少
 * 个袋子，如果无论如何都不能正好装下，返回-1.
 * 思路：
 * 思路1：输入n，直接用8类型的袋子看最多需要多少个，n/8，剩下的苹果是否能用6类型的袋子正
 * 好装下，如果不行，8类型袋子减少一个，剩下的苹果用6类型是否能装下，如果正好，那么答案出
 * 来了，如果都试完了还不行，直接返回-1；
 * 思路2：把apple从0-100打印出来，看规律，直接按照规律写代码
 *
 * @Author jiucaiyuan  2022/6/19 23:18
 * @mail services@jiucaiyuan.net
 */

public class AppleMinBags {

    /**
     * 思路1
     * @param apple
     * @return
     */
    public static int minBags(int apple) {
        if (apple < 0) {
            return -1;
        }
        int bag6 = -1;
        int bag8 = apple / 8;
        int rest = apple - bag8 * 8;

        while (bag8 > 0 && rest < 24) {
            int restUse6 = minBagBase6(rest);
            if (restUse6 != -1) {
                bag6 = restUse6;
                break;
            }
            rest = apple - (--bag8) * 8;
        }
        return bag6 == -1 ? -1 : bag6 + bag8;
    }

    /**
     * rest苹果正好用容量为6的袋子装下，返回袋子数，否则返回-1
     *
     * @param rest
     * @return
     */
    public static int minBagBase6(int rest) {
        return rest % 6 == 0 ? rest / 6 : -1;
    }
}

« 笔试题-牛羊吃草问题 | 递归DP-找零钱的方法数»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022