作者主页：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整数运算
- 基础贪心思想
初始代码
代码语言：javascript复制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个,购买方案:%sn",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个,购买方案:%sn",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个,购买方案:%sn",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。
若到弹簧的价格，则优先使用一元硬币，寻找是否可以完成购买。
若无法购买，则使用反向贪心的思想，弹簧总钱减去硬币价格这个值，让用到的硬币个数尽可能少，也就等价于弹簧价格用到的硬币个数尽可能多。
参考代码如下：
代码语言：javascript复制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个,购买方案:%sn",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个,购买方案:%sn",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个,购买方案:%sn",188888,66666,77777,88888,doWork(188888, 66666,77777, 88888));
}
}总结
要 AC 本题，必须学会基础贪心的算法，使用反向贪心的思想，弹簧总钱减去硬币价格这个值，让用到的硬币个数尽可能少，也就等价于弹簧价格用到的硬币个数尽可能多，最终通过本题。
