华硕编程竞赛11月JAVA专场 F题购买弹簧题解

Designer 小郑

发布于 2023-08-01 13:45:19

1500

发布于 2023-08-01 13:45:19

作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序

题目链接：题目链接

题面：

小王在体验完 ”自由弹簧“ 后，非常开心，想再玩一次，但厂家确告诉他试用已结束，如还需体验就要付费购买。

小王没有办法，只好拿出自己的零花钱，打算再购买一个 ”自由弹簧“，小王的零钱罐里都是一块、五块和十块的硬币，为了优化零钱罐的存储空间，小王打算使用尽可能多的硬币去购买 ”自由弹簧“。

假设 ”自由弹簧“ 的价格为 N 元，小王的零钱罐中分别含有 A 张一元硬币， B 张五元硬币， C 张十元硬币，其中 N、A、B、C都是小于100000的正整数。

小王想知道，如何支付 ”自由弹簧“ 的款项，才能让自己用掉尽可能多的硬币量？

该挑战输入 N、A、B、C 四个正整数，要求输出 o1（一元硬币的消耗量）、o5（五元硬币的消耗量）、o10（十元硬币的消耗量），若无法购买，则输出 oh my god。

本次挑战需要你至少了解一些 Java 中整数的基本运算，了解基本的贪心思想。

知识点

整数的基本运算
Java整数运算
基础贪心思想

初始代码

public class CMain {

    public static String doWork(int v,int num1,int num5,int num10) {
        //代码编辑区 开始
        return "oh my god";
        //代码编辑区 结尾
    }

    public static void main(String[] args) {
        //测试用例
        System.out.printf((Objects.equals("oh my god",doWork(6653,226,72,352)) ? "【√正确】" : "【X错误】") + "弹簧价格%d,①元硬币%d个,⑤元硬币%d个,⑩元硬币%d个,购买方案:%s\n",6653,226,72,352,doWork(6653,226,72,352));
        System.out.printf((Objects.equals("3 115 0",doWork(578, 5,127, 951)) ? "【√正确】" : "【X错误】") + "弹簧价格%d,①元硬币%d个,⑤元硬币%d个,⑩元硬币%d个,购买方案:%s\n",578,5,127,951,doWork(578, 5,127, 951));
        System.out.printf((Objects.equals("66663 24445 0",doWork(188888, 66666,77777, 88888)) ? "【√正确】" : "【X错误】") + "弹簧价格%d,①元硬币%d个,⑤元硬币%d个,⑩元硬币%d个,购买方案:%s\n",188888,66666,77777,88888,doWork(188888, 66666,77777, 88888));
    }
}

样例说明

输入 N、A、B、C 四个正整数，要求输出 o1（一元硬币的消耗量）、o5（五元硬币的消耗量）、o10（十元硬币的消耗量），若无法购买，则输出 oh my god。

如弹簧价格为 578，一元硬币有 5 个，五元硬币有 127 个，十元硬币为 951 个，则小王可以消耗 3 个一元硬币、115 个五元硬币、0 个十元硬币购买弹簧，最终输出 3 115 0。

如弹簧价格为 6653，一元硬币有 226 个，五元硬币有 72 个，十元硬币为 352 个，小王不能购买弹簧，输出 oh my god 。

题解

基础贪心题。先判断所有的硬币金额是否大于弹簧的价格，若不到弹簧的价格，则输出 oh my god。

若到弹簧的价格，则优先使用一元硬币，寻找是否可以完成购买。

若无法购买，则使用反向贪心的思想，弹簧总钱减去硬币价格这个值，让用到的硬币个数尽可能少，也就等价于弹簧价格用到的硬币个数尽可能多。

参考代码如下：

import java.util.Objects;

public class CAns {

    public static String doWork(int v,int num1,int num5,int num10) {
        // 代码编辑区 开始
        int c1 = 0, c5 = 0, c10 = 0;
        // 所有硬币加起来都小于价格
        if(num1 + num5 * 5+ num10 * 10 < v) {
            return "oh my god";
        }
        // 一元硬币可以满足价格
        if(num1 >= v) {
            c1 = v;
            return c1 + " " + c5 + " " + c10;
        }
        // 使用反向贪心的思想，弹簧总钱减去硬币价格这个值，让用到的硬币个数尽可能少，也就等价于弹簧价格用到的硬币个数尽可能多
        int sum = num1 + num5 * 5 + num10 * 10 - v;

        // 每次都选择面值最大的，这样钱的个数就最少
        int x = sum / 10;
        if(x > num10) {
            sum = sum - 10 * num10;
            x = 0;
        } else {
            sum = sum -10 * x;
            x = num10 - x;
        }

        int y= sum / 5;
        if(y > num5) {
            sum = sum - 5 * num5;
            y = 0;
        } else {
            sum = sum - y * 5;
            y= num5 - y;
        }
        int flag = 1;
        int z = sum;
        // 总价还小于价格，买不了
        if(z > num1) {
            flag=0;
        } else {
            sum = sum - z;
            z = num1 - z;
        }
        if(flag == 0) {
            return "oh my god";
        }
        return z + " " + y + " " + x;
    }

    public static void main(String[] args) {
        //测试用例
        System.out.printf((Objects.equals("oh my god",doWork(6653,226,72,352)) ? "【√正确】" : "【X错误】") + "弹簧价格%d,①元硬币%d个,⑤元硬币%d个,⑩元硬币%d个,购买方案:%s\n",6653,226,72,352,doWork(6653,226,72,352));
        System.out.printf((Objects.equals("3 115 0",doWork(578, 5,127, 951)) ? "【√正确】" : "【X错误】") + "弹簧价格%d,①元硬币%d个,⑤元硬币%d个,⑩元硬币%d个,购买方案:%s\n",578,5,127,951,doWork(578, 5,127, 951));
        System.out.printf((Objects.equals("66663 24445 0",doWork(188888, 66666,77777, 88888)) ? "【√正确】" : "【X错误】") + "弹簧价格%d,①元硬币%d个,⑤元硬币%d个,⑩元硬币%d个,购买方案:%s\n",188888,66666,77777,88888,doWork(188888, 66666,77777, 88888));
    }
}