我要成为毒奶牧高手！（Easy Version）

题目描述

【L2】传说是一款脍炙人口的卡牌游戏，有一个卡组名为毒奶牧，其核心卡牌名为 “枯萎之影” 拥有特殊的攻击机制，请计算最少需要多少次治疗操作才能击杀目标。

具体机制如下：

  • 枯萎之影的攻击力为 7 点。
  • 目标拥有护盾值（s）和生命值（b），其中生命值上限为 30 点。
  • 每次治疗+攻击的流程为：
    1. 先计算本次治疗的实际有效量：基于当前生命值（攻击前的生命值），治疗量固定为 3 点，但不能超过生命值上限 30 点（即实际治疗量 = min (3, 30 - 攻击前生命值)）。
    2. 枯萎之影进行攻击，优先消耗护盾值，护盾不足时剩余伤害直接扣除生命值。
    3. 若攻击后生命值 ≤ 0，则目标被击杀，本次治疗操作后的治疗效果不结算。
    4. 若攻击后生命值 > 0，则结算步骤 1 中计算的实际治疗量，增加到生命值中（不超过 30）。

给定目标的初始护盾值 s 和初始生命值 b，请问最少需要进行多少次治疗操作，才能让枯萎之影的攻击使目标生命值 ≤ 0（即击杀目标）？

输入格式

第一行输入一个整数 T（1 ≤ T ≤ 1e8），表示测试数据的组数。 每组测试数据输入两个整数 s 和 b，其中：

  • s 为初始护盾值（0 ≤ s ≤1e9）
  • b 为初始生命值（1 ≤ b ≤ 30）

输出格式

对于每组测试数据，输出一个整数，表示最少需要的治疗次数。

示例输入

1
2
3
4
5
6
5
0 7
0 8
7 1
14 30
1000000000 30

示例输出

1
2
3
4
5
1
2
2
8
142857149

————————————————————我是分割线———————————————————

下面是题解

————————————————————我是分割线———————————————————

题解

模拟法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int s, b;  // s: 护盾值, b: 生命值
        cin >> s >> b;
        int cnt = 0;  // 治疗次数
        while (b > 0) {  // 只要生命值>0就继续循环
            cnt++;
            int h = min(3, 30 - b);  // 计算本次治疗量
            int d = min(7, s);  // 计算护盾承受的伤害
            s -= d;  // 更新护盾值
            b -= 7 - d;  // 更新生命值(总伤害7 - 护盾承受的伤害)
            if (b > 0) b += h;  // 若攻击后未死亡，结算治疗效果
        }
        cout << cnt << endl;
    }
    return 0;
}

O (T*s)

优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long s, b;
        cin >> s >> b;
        long long cnt = 0;
        long long k1 = (s + 6) / 7;  // 向上取整计算护盾消耗次数
        long long full_attacks = (s % 7 == 0) ? k1 : k1 - 1;
        long long new_b = b;
        bool killed = false;

        // 计算护盾耗尽前的生命值变化
        for (long long i = 0; i < full_attacks; i++) {
    	long long h = min(3LL, 30LL - new_b);  // 治疗量
    	long long d = min(7LL, s);             // 护盾承受的伤害
    	new_b -= (7 - d);                      // 攻击后的生命值变化
    	if (new_b <= 0) {                      // 若生命值已降至0，直接输出结果
        	cout << i + 1 << endl;
        	killed = true;
        	break;
    	}
    	new_b += h;                            // 结算治疗（攻击后未死亡）
    	s -= d;                                // 更新护盾值
	}

        if (killed) continue;

        // 处理最后一次攻击（可能护盾已耗尽）
        if (s > 0) {
            long long h = min(3LL, 30LL - new_b);
            long long d = min(7LL, s);
            new_b -= (7 - d);
            if (new_b <= 0) {
                cout << k1 << endl;
                continue;
            }
            new_b += h;
            s -= d;
        }

        // 护盾已耗尽，计算剩余攻击次数
        long long k2 = 0;
        long long current_b = new_b;
        while (current_b > 0) {
            k2++;
            long long h = min(3LL, 30LL - current_b);
            current_b -= 7;
            if (current_b > 0) current_b += h;
        }

        cout << k1 + k2 << endl;
    }
    return 0;
}

O (T)

————————————————————我是分割线———————————————————

下面是困难版本

————————————————————我是分割线———————————————————

我要成为毒奶牧高手！（Hard Version）

题目描述

【L2】传说是一款脍炙人口的卡牌游戏，有一个卡组名为毒奶牧，其核心卡牌名为 “枯萎之影” 拥有特殊的攻击机制，请计算最少需要多少次治疗操作才能击杀目标。

  • 存在 n 个枯萎之影（n=1 或 n=2），若触发 “观鸟” 效果，单个枯萎之影的攻击力为 9 点；否则为 7 点。总伤害为单个伤害 × n。
  • 目标拥有护盾值（s）和生命值（b），其中生命值上限为 30 点。
  • 每次治疗 + 攻击的流程为：
    1. 先选择本次治疗方式（二选一，特殊治疗仅可使用一次）：
      • 普通治疗：计算实际有效量为 min (3, 30 - 攻击前生命值)。
      • 特殊治疗（仅可使用一次）：计算实际有效量为 min (2, 30 - 攻击前生命值)。
    2. 所有枯萎之影合计攻击，优先消耗护盾值，护盾不足时剩余伤害直接扣除生命值。
    3. 若攻击后生命值 ≤ 0，则目标被击杀，本次治疗操作后的治疗效果不结算。
    4. 若攻击后生命值 > 0，则结算步骤 1 中选择的治疗方式对应的实际治疗量，增加到生命值中（不超过 30）。

给定目标的初始护盾值 s、初始生命值 b、枯萎之影数量 n（1 或 2）、是否触发观鸟效果 f（0 或 1，1 表示单个伤害为 9，0 表示为 7），请问最少需要进行多少次治疗操作，才能使目标生命值 ≤ 0（即击杀目标）？

输入格式

第一行输入一个整数 T（1 ≤ T ≤ 1e5），表示测试数据的组数。 每组测试数据输入四个整数 s, b, n, f，其中：

  • s 为初始护盾值（0 ≤ s ≤ 1e9）
  • b 为初始生命值（1 ≤ b ≤ 30）
  • n 为枯萎之影数量（1 或 2）
  • f 为观鸟效果（0 或 1，1 表示单个伤害为 9，0 表示为 7）

输出格式

对于每组测试数据，输出一个整数，表示最少需要的治疗次数。

示例输入

1
2
3
4
5
6
5
0 5 1 0
3 9 1 0
0 8 1 1
20 30 2 1
100 1 1 0

示例输出

1
2
3
4
5
1
2
1
3
21

示例输入

1
2
3
4
5
6
7
6
5 7 1 0
0 30 1 0
18 15 2 1
0 10 1 0
0 13 1 0
100 5 1 0

示例输出

1
2
3
4
5
6
2
6
2
2
3
21

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
// 向上取整：ceil(a / b)
inline int ceil_div(int a, int b) {
    return (a + b - 1) / b;
}
// 计算无护盾阶段的步数（已知当前生命值，返回从当前步开始的击杀步数）
int simulate_no_shield(int health, int d, bool& used_special, int special_pos, int current_step) {
    int steps = 0;
    int h = health;
    while (true) {
        steps++;
        int current_total_step = current_step + steps;
        // 计算本次治疗量
        int heal;
        if (current_total_step == special_pos && !used_special) {
            heal = min(2, 30 - h);
            used_special = true;
        } else {
            heal = min(3, 30 - h);
        }
        // 攻击（无护盾，直接扣血）
        h -= d;
        if (h <= 0) {
            // 若使用了特殊治疗或不使用，返回步数
            if (special_pos == -1 || used_special) return steps;
            else return INT_MAX;
        }
        // 治疗生效
        h = min(h + heal, 30);
    }
}
// 模拟函数：special_pos=-1表示不使用特殊治疗，否则为使用步数
int simulate(int s, int b, int d, int special_pos) {
    if (d == 0) return INT_MAX; // 无效伤害
    // 1. 计算护盾阶段参数
    int m = (s == 0) ? 0 : ceil_div(s, d); // 消耗护盾总步数
    bool used_special = (special_pos == -1); // 是否使用特殊治疗
    int current_step = 0;
    int h = b; // 当前生命值
    // 2. 处理护盾阶段（前m-1步）
    if (m > 0) {
        int steps_shield = m - 1; // 护盾阶段前m-1步
        // 计算前m-1步的生命值（普通治疗为主，除非特殊治疗在这阶段）
        if (special_pos <= steps_shield && special_pos != -1) {
            // 特殊治疗在护盾阶段的前m-1步内：前k-1步普通治疗，第k步特殊治疗
            int k = special_pos;
            if (k < 1 || k > steps_shield) {
                // 特殊治疗位置无效（不在前m-1步），按普通治疗计算
                h = min(h + 3 * steps_shield, 30);
            } else {
                // 前k-1步普通治疗，第k步特殊治疗，剩余steps_shield - k步普通治疗
                int add = 3 * (k - 1) + 2 + 3 * (steps_shield - k);
                h = min(h + add, 30);
                used_special = true;
            }
        } else {
            // 前m-1步均为普通治疗
            h = min(h + 3 * steps_shield, 30);
        }
        current_step = steps_shield; // 已完成steps_shield步
    }
    // 3. 处理第m步（护盾耗尽步）
    if (m > 0) {
        current_step++; // 进入第m步
        // 计算第m步攻击的剩余伤害（护盾耗尽后作用于生命值）
        int shield_remaining = s - (m - 1) * d; // 第m步前剩余护盾
        int damage_to_health = d - shield_remaining; // 护盾耗尽后扣血
        // 第m步的治疗量
        int heal;
        if (current_step == special_pos && !used_special) {
            heal = min(2, 30 - h);
            used_special = true;
        } else {
            heal = min(3, 30 - h);
        }
        // 第m步攻击后生命值
        int h_after_attack = h - damage_to_health;
        if (h_after_attack <= 0) {
            // 第m步直接击杀
            if (special_pos == -1 || used_special) return current_step;
            else return INT_MAX;
        }
        // 第m步治疗生效（未击杀）
        h = min(h_after_attack + heal, 30);
    }
    // 4. 进入无护盾阶段，模拟剩余步骤
    int steps_no_shield = simulate_no_shield(h, d, used_special, special_pos, current_step);
    if (steps_no_shield == INT_MAX) return INT_MAX;
    return current_step + steps_no_shield;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int s, b, n, f;
        cin >> s >> b >> n >> f;
        int d = (f ? 9 : 7) * n;
        // 不使用特殊治疗
        int min_steps = simulate(s, b, d, -1);
        // 枚举特殊治疗位置（范围：1到m+200，m为护盾阶段步数，200为无护盾阶段冗余）
        int m = (s == 0) ? 0 : ceil_div(s, d);
        int max_enum = m + 200; // 限制枚举范围，避免无效计算
        for (int k = 1; k <= max_enum; k++) {
            int steps = simulate(s, b, d, k);
            if (steps < min_steps) {
                min_steps = steps;
            }
        }
        cout << min_steps << '\n';
    }
    return 0;
}

O(T * m )

dp优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
using namespace std;

int main() {
    vector<vector<int>> dp_norm_list;
    vector<vector<int>> dp_used_list;
    vector<int> pers = {7, 9, 14, 18};
    for (int idx = 0; idx < 4; idx++) {
        int per = pers[idx];
        vector<int> dp_norm(31, INT_MAX);
        vector<int> dp_used(31, INT_MAX);
        for (int i = 1; i <= 30; i++) {
            int h = min(3, 30 - i);
            int after_attack = i - per;
            if (after_attack <= 0) {
                dp_used[i] = 1;
            } else {
                int next_state = after_attack + h;
                if (next_state > 30) next_state = 30;
                dp_used[i] = 1 + dp_used[next_state];
            }
        }
        for (int i = 1; i <= 30; i++) {
            int option1, option2;
            int h1 = min(3, 30 - i);
            int after_attack1 = i - per;
            if (after_attack1 <= 0) {
                option1 = 1;
            } else {
                int next_state1 = after_attack1 + h1;
                if (next_state1 > 30) next_state1 = 30;
                option1 = 1 + dp_norm[next_state1];
            }
            int h2 = min(2, 30 - i);
            int after_attack2 = i - per;
            if (after_attack2 <= 0) {
                option2 = 1;
            } else {
                int next_state2 = after_attack2 + h2;
                if (next_state2 > 30) next_state2 = 30;
                option2 = 1 + dp_used[next_state2];
            }
            dp_norm[i] = min(option1, option2);
        }
        dp_norm_list.push_back(dp_norm);
        dp_used_list.push_back(dp_used);
    }

    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long s, b;
        int n, f;
        cin >> s >> b >> n >> f;
        int per;
        int idx_per;
        if (n == 1 && f == 0) {
            per = 7;
            idx_per = 0;
        } else if (n == 1 && f == 1) {
            per = 9;
            idx_per = 1;
        } else if (n == 2 && f == 0) {
            per = 14;
            idx_per = 2;
        } else {
            per = 18;
            idx_per = 3;
        }

        vector<int>& dp_norm = dp_norm_list[idx_per];
        vector<int>& dp_used = dp_used_list[idx_per];
        long long k1 = 0;
        if (s > 0) {
            k1 = (s + per - 1) / per;
        }

        if (k1 == 0) {
            long long total0, total2;
            int h0 = min(3, 30 - (int)b);
            long long after_attack = b - per;
            if (after_attack <= 0) {
                total0 = 1;
            } else {
                total0 = 1 + dp_norm[after_attack + h0];
            }
            int h2 = min(2, 30 - (int)b);
            after_attack = b - per;
            if (after_attack <= 0) {
                total2 = 1;
            } else {
                total2 = 1 + dp_used[after_attack + h2];
            }
            long long ans = min(total0, total2);
            cout << ans << '\n';
        } else {
            long long total0 = LLONG_MAX;
            long long total1 = LLONG_MAX;
            long long total2 = LLONG_MAX;

            long long life0 = b + 3 * (k1 - 1);
            if (life0 > 30) life0 = 30;
            int heal0 = min(3, 30 - (int)life0);
            long long damage_in_last = k1 * (long long)per - s;
            long long after_attack0 = life0 - damage_in_last;
            if (after_attack0 <= 0) {
                total0 = k1;
            } else {
                long long next_state0 = after_attack0 + heal0;
                if (next_state0 > 30) next_state0 = 30;
                total0 = k1 + dp_norm[next_state0];
            }

            long long life1 = life0;
            int heal1 = min(2, 30 - (int)life1);
            long long after_attack1 = life1 - damage_in_last;
            if (after_attack1 <= 0) {
                total1 = k1;
            } else {
                long long next_state1 = after_attack1 + heal1;
                if (next_state1 > 30) next_state1 = 30;
                total1 = k1 + dp_used[next_state1];
            }

            if (k1 >= 2) {
                long long life2 = b + 3 * (k1 - 1) - 1;
                if (life2 > 30) life2 = 30;
                int heal2 = min(3, 30 - (int)life2);
                long long after_attack2 = life2 - damage_in_last;
                if (after_attack2 <= 0) {
                    total2 = k1;
                } else {
                    long long next_state2 = after_attack2 + heal2;
                    if (next_state2 > 30) next_state2 = 30;
                    total2 = k1 + dp_used[next_state2];
                }
            }

            long long ans = min(total0, min(total1, total2));
            cout << ans << '\n';
        }
    }
    return 0;
}

通过预处理 DP 表（覆盖 4 种固定伤害、1-30 生命值的两种状态），公式直接计算护盾阶段状态，无护盾阶段直接查表得结果，省去实时模拟，将单测试用例计算压至 O (1)，大幅优化效率。O（T）