曙蹗查看:4 回复:4 评论:4 创建时间:2023-12-31T10:37:11用户:曙蹗查看:4 回复:4 评论:4 创建时间:2023-12-31T10:37:11
题目描述
小明正在玩一款名为仙剑奇侠传的游戏。
他已经打到最终boss拜月教主处了。
小明操控的李逍遥现在包裹里既有武器又有道具，他有以下攻击手段：
- 使用道具对拜月教主造成伤害，道具使用一次后消失。
- 使用剑普攻攻击对拜月教主造成伤害，剑可以进行无限次普通攻击。
- 投掷剑对拜月教主造成伤害，剑投掷后消失。
为了方便描述此题，现做以下说明：
- 我们认为所有剑有两种属性 a 和 b，分别表示该剑的普通攻击能造成的伤害和投掷能造成的伤害。
- 道具可以看做只能进行投掷不能进行普通攻击的剑，即其属性 a=0。下面所有描述把道具视作剑的一种。
- 李逍遥共有 n 把剑（道具当作剑处理）。其中第 i 把剑的属性为 ai, bi。
- 拜月教主初始血量为 x，当其血量变为 0 或 0 以下时视作被打败。
- 每个回合李逍遥需要选择一把剑进行普通攻击或投掷，如果选择第 i 把剑普通攻击，则造成 ai 点伤害；如果选择投掷，则造成 bi 点伤害，且投掷后该把剑消失。
请你帮助小明计算李逍遥打败拜月教主所需的最小回合数。
输入共 n+1 行。
第一行两个整数 n，x 分别表示剑/道具的数量和拜月教主的初始血量。
接下来 n 行，每行两个数表示第 i 把剑的普攻伤害 ai 和投掷伤害 bi。（如果 ai=0 表示该剑为道具）
输出一行一个数表示打败拜月教主所需的最小回合数。
输入输出样例 输入样例#1：1 5 1 2输出样例#1：
4输入样例#2：
2 10 5 4 2 7输出样例#2：
2输入样例#3：
10 1000 93 100 54 291 74 100 4 100 92 57 48 100 100 93 10 117 57 110 17 100输出样例#3：
8补充说明 【样例解释】
阿克星的大黄kun_提供一种思路吧。也不知道对不对
题目只要求尽快打败对方，可以把一把剑分为两把剑。定义结构体node 中含有两个成员，u，v;u带表这把剑一次攻击造成的伤害，v代表这把剑是只攻击一次或攻击无限次，对于题目中给出的ai,bi，定义两个node类型的结构体x,y。x.u=ai,x.v=1,y.u=ai,y.v=2;然后把两个结构体插入到一个数组c末尾
以结构题中的u为关键字进行排序，然后从前往后扫描数组
1.如果ci.v=1,就令n-=ci.u;
2.如果ci.v=2,就输出ceil(n*1.0/ci.u),return 0,其中ceil（double x）表示返回浮点数x向上取整的结果
应该是一道小贪心算法题目，入门难度左右
点赞0
评论
一个STUB用户_7236882OK，完全不会呢。请出神奇的GPT来帮你。
这是动态规划问题。可以使用一个一维数组dp来记录每个血量状态所需的最小回合数。
首先，我们初始化dp数组，将所有位置的值设置为无穷大。
然后，我们从血量为0开始向上遍历，计算每个血量状态所需的最小回合数。对于每个血量状态，我们遍历所有剑的属性，计算普通攻击和投掷的伤害，并更新dp数组中对应的位置的值。
最后，我们返回dp数组中血量为x时的值，即打败拜月教主所需的最小回合数。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
vector<int> dp(x + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= x; ++i) {
for (int j = 0; j < n; ++j) {
if (i >= a[j]) {
dp[i] = min(dp[i], dp[i - a[j]] + 1);
}
if (i >= b[j]) {
dp[i] = min(dp[i], dp[i - b[j]] + 1);
}
}
}
cout << dp[x] << endl;
return 0;
}
这段代码的时间复杂度为O(nx)，其中n是剑的数量，x是拜月教主的初始血量。
点赞0
评论
