专栏文章

题解:P12192 [NOISG 2025 Prelim] Train Or Bus

P12192题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipluozm
此快照首次捕获于
2025/12/03 14:07
3 个月前
此快照最后确认于
2025/12/03 14:07
3 个月前
查看原文

最近刚好学了贪心,那就切一下吧

CPP
#include<bits/stdc++.h>
using namespace std;
int main() {
    // 读取城市数量 n
    itn n;
    cin >> n;
    // 定义两个数组 a 和 b,分别存储火车和公交的耗时
    vector<int> a(n), b(n);
    // 读取火车耗时 a[0..n-1]
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    // 读取公交耗时 b[0..n-1]
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    // 计算总最短时间
    int total_time = 0;
    for (int i = 0; i < n; ++i) {
        // 对每一段路,选择耗时更短的交通工具
        total_time += min(a[i], b[i]);
    }
    // 输出结果
    cout << total_time << endl;
    return 0;
}

代码解释

AC记录

‌输入处理‌:

读取 nn ,然后读取 nna[i]a[i]nnb[i]b[i] 。 ‌计算最短时间‌:
遍历每一段路i,选择 a[i]a[i]b[i]b[i] 中的较小值,累加到total_time。

‌输出结果‌:

直接输出total_time。
复杂度分析

‌时间复杂度‌:

O(n)O(n) ,因为只需要遍历 nn 段路,每次取最小值的时间是 O(1)O(1)

‌空间复杂度‌:

O(n)O(n) ,用于存储 aabb 数组。
这道题的关键在于‌每一步选择更快的交通工具‌,由于选择是独立的,所以可以直接用 贪心算法贪心算法 解决。 动态规划动态规划 虽然也可以,但在这里显得多余。
此身第一篇题解!!!望管理员通过
有个小小错误,那就用来防抄袭吧

评论

0 条评论,欢迎与作者交流。

正在加载评论...