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

╰+哭是因爲堅強的太久メ 2023-09-24 15:24 66阅读 0赞

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

题目链接：[题目链接][Link 1]

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题面： ###

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

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

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

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

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

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

### 知识点 ###

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

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 初始代码 ###

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));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 样例说明 ###

输入 `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` 。

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题解 ###

基础贪心题。先判断所有的硬币金额是否大于弹簧的价格，若不到弹簧的价格，则输出 `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));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 总结 ###

要 AC 本题，必须学会**基础贪心**的算法，使用反向贪心的思想，弹簧总钱减去硬币价格这个值，让用到的硬币个数尽可能少，也就等价于弹簧价格用到的硬币个数尽可能多，最终通过本题。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[Link 1]: https://www.lanqiao.cn/contests/lqENT05/challenges/
[d20811fc24154b148e6372d8bd803dab.png_pic_center]: https://img-blog.csdnimg.cn/d20811fc24154b148e6372d8bd803dab.png#pic_center
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center