面试遇到一个问题，求大佬帮忙解答下。
现在有 3 只怪兽，他们的都有自己的血量a,b,c(1<=a,b,c<=100)，当Tom 打死第一怪兽的时候花费的代价为 0，其余的怪兽的代价为当前的怪兽的血量减去上一个怪兽的血量的绝对值。问 Tom 打死这些怪兽所需要的最小代价 ? 分别输入三只怪兽的血量；输出打死三只怪兽的最小代价。
展开
收起
1
条回答
写回答
写回答
-
应该使用贪心算法完成，策略是每次打怪兽都选择代价最小的一只。由于第一次打怪兽的花费为 0，所以第一次可以打血量最小的（最大的也可以），接下来每次选择怪兽的时候就可以选择花费代价最小的。由于每次打怪兽的代价都是：当前怪兽的血量和上一个怪兽的血量的差的绝对值。于是可以得出结论，最小代价为所有怪兽血量的最大值减最小值。 则输入：2,5,8
输出：6。2021-12-23 18:14:53赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
