题目链接：题目链接
题面：
小王在体验完 ”自由弹簧“ 后，非常开心，想再玩一次，但厂家确告诉他试用已结束，如还需体验就要付费购买。
小王没有办法，只好拿出自己的零花钱，打算再购买一个 ”自由弹簧“，小王的零钱罐里都是一块、五块和十块的硬币，为了优化零钱罐的存储空间，小王打算使用尽可能多的硬币去购买 ”自由弹簧“。
假设 ”自由弹簧“ 的价格为 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)); } }
总结
要 AC 本题，必须学会基础贪心的算法，使用反向贪心的思想，弹簧总钱减去硬币价格这个值，让用到的硬币个数尽可能少，也就等价于弹簧价格用到的硬币个数尽可能多，最终通过本题。
