【C++】B2066救援题目分析和解决讲解

💯前言

• 在本文中，我们将对一道来自洛谷编程题目“B2066 救援”进行全面分析和解决，包括题目内容释义，解决思路，以及代码运行中的更新与优化过程。对于解题过程中出现的问题，我们进行了不同方案比较，并给出了细致的解析和解决方式。通过本文，读者将能学习如何分析一道复合题，如何检查代码中的问题，以及如何使解决方案更加精准和高效。
  以下是我们对题目《B2066 救援》的分析和全过程解决。
  C++ 参考手册
  

💯 题目

B2066 救援

救援

题目描述

救生船从大本营出发，营救若干屋顶上的人回到大本营，屋顶数目以及每个屋顶的坐标。

和人数都将由输入决定，求出所有人都到达大本营并登陆所用的时间。

在直角坐标系的原点是大本营，救生船每次从大本营出发，救了人之后将人送回大本营。坐标系中的点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。救生船每次从大本营出发，以速度 $50$ 米 / 分钟驾向下一屋顶，达到一屋顶后，救下其上的所有人，每人上船 $1$ 分钟，船原路返回，达到大本营，每人下船 $0.5$ 分钟。假设原点与任意一个屋顶的连线不突过其它屋顶。

输入格式

第一行，一个整数，表示屋顶数 $n$。

接下来会有 $n$ 行输入，每一行上包含两个表示屋顶相对于大本营的平面坐标位置的实数（单位是米）、一个表示人数的整数，数之间以一个空格分开。

输出格式

一行，救援需要的总时间，精确到分钟（向上取整）。

样例 #1

样例输入 #1

1
30 40 3

样例输出 #1

7

💯 题目分析

该题目基本问题背景是：在直角坐标系中，大本营作为原点，救生船需要去回不同屋顶，将上面的人救回大本营，每个屋顶的坐标和人数由输入确定。救援时间由下列团队操作减反处理：

每个屋顶计算的元素

1. 每个屋顶和大本营的相实坐标跑，在平面坐标系中远离：
   $\text{Distance}=\sqrt{x^2+y^2}$

2. 进出和退场时间：
   $\text{Travel Time (Round Trip)}=2\cdot \frac{\text{Distance}}{50}$

3. 每个人上船和下船的时间：
   $\text{Load Time}=\text{People}\cdot (1+0.5)=\text{People}\cdot 1.5$

总时间实际上为：
$\text{Total Time per Roof}=2\cdot \frac{\text{Distance}}{50}+\text{People}\cdot 1.5$

最终，精确到分钟，需要向上取整：
$\text{Final Time}=\lceil \text{Total Time per Roof}\rceil$

💯 思路解析

将解题分为下列步骤：

1. 读取输入

• 第一行读取 $n$，表示屋顶总数。
• 接下来的 $n$ 行读取每个屋顶的坐标 $(x,y)$ 和人数 $r$。

2. 计算屋顶时间

• 根据坐标计算屋顶和大本营的相实距离：
  $\text{Distance}=\sqrt{x^2+y^2}$
• 根据上面公式计算每个屋顶的时间并精确到分钟：
  $\text{Time}=(\text{Distance}/50)\times 2+r\times 1.5$

3. 结果精确取整

• 将所有屋顶的时间紧总和，并通过向上取整。

💯 完整解决代码

使用 C++ 实现：

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n; // 屋顶数量
    cin >> n;

    double total_time = 0; // 总时间初始化为 0

    for (int i = 0; i < n; i++) {
        double x, y; // 坐标
        int r;       // 人数
        cin >> x >> y >> r;

        // 计算到屋顶的距离
        double distance = sqrt(x * x + y * y);

        // 计算单个屋顶所需时间
        double time = (distance / 50) * 2 + r * 1.5;

        // 紧总时间
        total_time += ceil(time);
    }

    // 输出总时间
    cout << (int)ceil(total_time) << endl;

    return 0;
}

💯 突出问题分析

在实现过程中，出现过一些更新和优化，重点如下：

1. 选择正确的数据类型

调查发现，如果屋顶坐标和距离用 int，在解析输入为浮点数时，将会丢失精度。

解决方案

将坐标声明为浮点型：

double x, y;

2. 取整的位置

有些方案在屋顶时间总和时才取整，导致粘进值问题。

优化思路

在计算单个屋顶时就取整：

total_time += ceil(time);

3. 边界情况处理

• 如果输入 $n=0$，必须特别处理：

if (n == 0) {
    cout << 0 << endl;
    return 0;
}

• 如果人数为 $0$，只计算距离时间，不要含及上船和下船。

💯 复杂度分析

1. 时间复杂度

• 输入为 $n$ 个屋顶，每个屋顶计算距离和时间，复杂度为：
  $O(n)$

2. 空间复杂度

• 只使用常数量的变量，空间复杂度为：
  $O(1)$

💯 学习收获和应用

通过该题目，我们学习到如下点：

1. 在复杂场景中分解问题的思路：通过分解每个屋顶的时间，将复杂问题分解为许多小问题。
2. 选择正确的数据类型：特别是处理浮点数时，需要保证计算精度。
3. 处理边界情况：在突出输入时，须要考虑特殊情况，如屋顶数量为 0 或人数为 0。

💯 小结

通过该题目解决，我们基于 C++ 给出了进一步的优化，包括类型选择、取整位置和边界情况处理。这些优化不仅能解决本题，对于复杂程序进一步深入优化也具有往往运用实际意义。