16. 小红闯关
题目描述
小红正在玩一个有 n 个关卡的游戏。通过第 i 个关卡通常需要消耗 ai 个单位的时间。小红必须按照从前往后的顺序依次通过每一个关卡。
特殊机制
- 道具获取: 每通过 k 个关卡(无论是消耗时间通过还是使用道具通过),小红都会获得一个“跳关道具”。
- 道具效果: 跳关道具可以在任意一个关卡使用。使用后,可以不消耗任何时间直接通过该关卡。
问题
请问小红通过全部 n 个关卡,最少需要消耗多少单位时间?
解
这题还是挺难的,主要是跳关道具必须在完成第 mk 个关卡以后才能使用,因此这题不能单纯地找最大值,例如,我们在 [k,2k] 之间找到了整个数组里前 t 大数的 k 个,但是手里只有一个跳关道具,因此这剩下的 k−1 个就必须手动通关了。
关键的思路在于,如果我们不找最大值,而是找最小值,可不可以呢?
从头开始遍历数组,我们先假设当前的关卡需要被跳过,并维护一个小根堆用来存储(暂定)被跳过的关卡。
接着,我们通过 ⌊ki⌋ 判断当前最大可使用的道具,如果堆的大小超过当前限制,就放弃跳过消耗最小的那个关卡。
这样做的好处是,我们既动态地维护了数据结构,保证每个节点在被跳过时都符合当前确实有道具可用的情况。同时,我们也解决了道具不必即时使用的问题。
如果我们想的是:拿着道具,并在接下来的一段路的最大值使用它,那么问题来了,我们要如何知道下一个最大值出现在哪里呢?这里需要 O(n) 判断,总时间复杂度 O(n2) 。
我们在这里成功地运用了逆向思维:我们首先假设所有关卡都使用道具跳过,在不满足跳过条件时,再把那个关卡的“债”还了。笔者感觉很有意思,遂记录。
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
| #include <iostream>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;
/**
* 解决思路:
* 使用最小堆维护当前已经选择跳过的关卡耗时。
* 遍历到第 i 个关卡(0-indexed)时,我们已经完成了 i 关,
* 因此手中累计获得的道具上限为 i / k。
*/
void solve() {
int n, k;
if (!(cin >> n >> k)) return;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// 最小堆,存储当前被跳过的关卡的耗时
priority_queue<long long, vector<long long>, greater<long long>> skipped_levels;
long long total_time = 0;
for (int i = 0; i < n; ++i) {
// 先假设当前这一关我们要跳过
skipped_levels.push(a[i]);
// 计算当前允许的最大跳关次数
int max_allowed_skips = i / k;
// 如果堆的大小超过了当前拥有的道具数,
// 则必须从堆中弹出一个耗时最小的关卡改为“手动通关”
if (skipped_levels.size() > (size_t)max_allowed_skips) {
total_time += skipped_levels.top();
skipped_levels.pop();
}
}
cout << total_time << endl;
}
int main() {
// 优化标准流输入输出性能
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
|
17. 小苯的子串删除
题目描述
小苯有一个长度为 n 的数字串 s。他的目标是通过删除操作,使得剩余数字拼接成的数是 3 的倍数。
操作规则
小苯可以进行最多一次操作:
- 选择一段区间 [l,r](1≤l≤r≤n);
- 删除该区间内的所有数位 sl,sl+1,…,sr。
问题
请你计算有多少种不同的删除区间方案 [l,r],能够使删除后的数字串满足是 3 的倍数。
注意事项
- 特殊情况: 如果删除后数字串为空,小苯认为它也是 3 的倍数。
- 目标: 统计所有符合条件的 (l,r) 对的数量。
解
数学模型:
假设原始字符串的数字总和为 S。当我们删除区间 [l,r] 时,剩余部分的数字之和为 S−(区间 [l,r] 的和)。
我们的目标是让:
(S−i=l∑rai)≡0(mod3)这也等价于:
i=l∑rai≡S(mod3)也就是说,我们需要找出的所有子区间,其内部数字之和对3取模的结果必须等于整个字符串总和对3取模的结果。
前缀和转化:
设 P[i] 为前 i 个数字的和模3的结果(规定 P[0]=0)。
区间 [l,r] 的和模3的结果可以表示为:(P[r]−P[l−1])(mod3)。
我们要找满足以下条件的 (l,r) 组合:
(P[r]−P[l−1])≡S(mod3)算法效率:
如果用双重循环枚举 l 和 r,复杂度是 O(n2),对于较大的 n(如 105 以上)会超时。
我们可以利用哈希表或频率数组记录前缀和出现的次数,将复杂度优化到 O(n)。
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
| #include <iostream>
#include <string>
#include <vector>
using namespace std;
long long solve() {
string s;
if (!(cin >> s)) return 0;
int n = s.length();
// 计算总和 S 模 3 的结果
int total_sum_mod3 = 0;
for (char c : s) {
total_sum_mod3 = (total_sum_mod3 + (c - '0')) % 3;
}
// 特殊情况:如果总和已经是3的倍数,我们要找区间和模3等于0的子区间
// 目标:(P[r] - P[l-1]) % 3 == total_sum_mod3
// count[v] 记录前缀和模 3 等于 v 的出现次数
vector<long long> count(3, 0);
count[0] = 1; // 初始前缀和 P[0] = 0
int current_prefix_sum = 0;
long long ans = 0;
for (int i = 0; i < n; ++i) {
// 更新当前前缀和
current_prefix_sum = (current_prefix_sum + (s[i] - '0')) % 3;
// 我们需要找到之前的某个前缀和 prev_prefix_sum 使得:
// (current_prefix_sum - prev_prefix_sum + 3) % 3 == total_sum_mod3
// 移项得:
int target = (current_prefix_sum - total_sum_mod3 + 3) % 3;
// 累加之前出现过多少次这个 target
ans += count[target];
// 记录当前前缀和出现的次数
count[current_prefix_sum]++;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << "请输入数字串: ";
cout << "\n满足条件的操作数: " << solve() << endl;
return 0;
}
|