陶陶最近在玩这样的一种卡牌游戏,具体游戏规则如下: 卡牌中有若干张 A/2/3/4/5/6/7/8/9/10/J/Q/K 牌,点数分别为 1 至 13 点 弃置一张卡牌,并对敌军造成伤害,卡牌所能造成的伤害为卡牌的点数 初始时陶陶会获得 N 张卡牌,并且会产生一张生命值为 M 的敌军卡牌,陶陶需要利用自己的手牌将敌军消灭,在消灭敌军的同时需要保证自己所剩下的卡牌点数之和尽可能大,陶陶想知道自己在消灭敌军完后剩余卡牌点数之和的最大值(若无法消灭,请输出 - 1),请你帮帮他。
时间: 2024-01-05 09:03:11 浏览: 338
这道题可以使用贪心和排序的思想来解决。
首先,我们可以将手牌按照点数从大到小排序,这样可以保证我们在使用手牌时尽可能地使用点数更大的卡牌来攻击敌军,从而使剩余的卡牌点数之和更大。
然后,我们可以依次使用手牌来攻击敌军,直到敌军的生命值为 0 或者我们的手牌已经用完为止。如果最后敌军的生命值为 0,那么剩余的卡牌点数之和就是我们要求的答案;如果最后敌军的生命值不为 0,那么说明我们无法消灭敌军,答案输出 -1。
以下是一份 C++ 代码实现,其中 cards 数组存储了手牌的点数,n 表示手牌的数量,m 表示敌军的生命值:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int cards[n];
for (int i = 0; i < n; i++) {
cin >> cards[i];
}
// 将手牌按照点数从大到小排序
sort(cards, cards + n, greater<int>());
int sum = 0;
for (int i = 0; i < n; i++) {
// 如果敌军已经死亡,直接退出循环
if (m <= 0) {
break;
}
// 使用当前手牌攻击敌军
m -= cards[i];
sum += cards[i];
}
// 判断是否成功消灭敌军
if (m <= 0) {
cout << sum << endl;
} else {
cout << -1 << endl;
}
return 0;
}
```
这个算法的时间复杂度是 O(nlogn),其中 n 表示手牌的数量,主要是排序的时间复杂度。
阅读全文