晋城企业网站建设,龙岩建设局网站声明,二级建造师证报考要求,手机网站布局题意#xff1a; 某A有一个剑 坚韧度为m 他可以用这个剑去攻打别的队伍 杀掉第 i 个队伍需要消耗的坚韧度为 Ai 并可以用得到的剑去打别的队(Bi个) 但是打完别的队这个剑就不能用了 问怎么用最少的坚韧度击败最多的队伍 给出T组样例 每个样例给出n m n表示有n个队 接下来n行给…题意 某A有一个剑 坚韧度为m 他可以用这个剑去攻打别的队伍 杀掉第 i 个队伍需要消耗的坚韧度为 Ai 并可以用得到的剑去打别的队(Bi个) 但是打完别的队这个剑就不能用了 问怎么用最少的坚韧度击败最多的队伍 给出T组样例 每个样例给出n m n表示有n个队 接下来n行给出Ai Bi 表示杀掉这个队需要消耗的坚韧度和杀掉这个队可以得到的剑可以杀的队伍数 输出可以杀掉的最多的队和最少花费的坚韧度 思路 可以想到的就是 杀掉一个bi ! 0理论上就可以杀掉所有 bi ! 0 的队伍 ×××××错的思路.. 把bi ! 0 和 bi 0分成两组 先用把一个bi ! 0里需要用的坚韧度最少的队伍杀掉..然后用得到的剑杀掉别的bi ! 0的队伍 然后用这些剑去把 bi 0 的杀掉 当这些得到的剑用完之后就用自己的剑尽量多得把别的队伍杀掉 ×××××反思ing.. 这个方法没考虑到的问题就是 4 2 1 1 1 1 1 0 7 0 这组数据如果用上面的思路 结果就会是 3 1 而最优解应该是 4 2 问题就出在得到的剑可能不用来杀 bi ! 0而用来杀 bi 0但是需要的坚韧度 ai 大的队伍 可以得到更好的答案 所以 √√√√√√√√√√√√√√√正确的思路 分两种情况考虑 ①. 只杀 bi 0 的队伍 ②. 杀 bi ! 0 和 bi 0的队伍 这样就要考虑有多少个 bi ! 0的队伍是用自己的剑杀的 所以应该分两种情况求值 然后第二种情况就遍历用自己的剑杀多少个bi 0 的队伍 求得最优解 Tips 好吧~我表示我的变量总是弄错 这道题主要是把 bi 0 和 bi ! 0 分组讨论 Code View Code 题目链接转载于:https://www.cnblogs.com/Griselda/archive/2012/09/26/2704614.html
