历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1123. 铲雪车原题链接简单

作者：

Equation_6 , 2025-03-24 17:08:46 ·山西 , 所有人可见 , 阅读 1

题解：铲雪车问题

一、题目背景

城市道路为双向车道，都需铲雪，但只有一辆铲雪车。铲雪车从停放处出发，开过的地方雪会被铲干净，要计算铲完所有道路积雪的最少时间。

二、解题思路

本题可将道路看作图的边，通过计算每条道路的长度，累加得到总路程，再根据铲雪车铲雪时的速度计算所需时间。因为道路是双向的，所以每条道路长度需计算两次。最后将总路程除以速度并进行单位换算，得到所需的小时和分钟数。

具体步骤如下：
1. 定义变量，用于存储铲雪车停放坐标和道路端点坐标，以及总路程 sum。
2. 读取铲雪车的停放坐标 x1 和 y1。
3. 循环读取每条道路的起点坐标 (x1, y1) 和终点坐标 (x2, y2)：
- 根据两点间距离公式 d = √((x1 - x2)² + (y1 - y2)²) 计算道路长度，由于是双向车道，将长度乘以 2 后累加到总路程 sum 中。
4. 计算总时间：
- 先将总路程 sum 的单位从米转换为千米，然后除以铲雪车铲雪时的速度 20 千米/时，得到总小时数。
- 将总小时数乘以 60 转换为分钟数，用 round 函数进行四舍五入取整。
- 计算小时数 hours 和剩余分钟数 minutes。
5. 按照指定格式输出小时和分钟。

三、代码逐段分析

（一）头文件和命名空间

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

包含了字符串操作（cstring）、输入输出（iostream）、算法（algorithm）和数学运算（cmath，用于开方等操作）相关的头文件，并使用标准命名空间。

（二）`main` 函数

int main()
{
    double x1, y1, x2, y2;
    cin >> x1 >> y1;

    double sum = 0;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        double dx = x1 - x2;
        double dy = y1 - y2;
        sum += sqrt(dx * dx + dy * dy) * 2;
    }

    int minutes = round(sum / 1000 / 20 * 60);
    int hours = minutes / 60;
    minutes %= 60;

    printf("%d:%02d\n", hours, minutes);

    return 0;
}

定义变量 x1、y1、x2、y2 用于存储坐标，读取铲雪车的停放坐标。
初始化总路程 sum = 0，进入循环读取道路信息：
- 计算道路两端点在 x 轴和 y 轴方向上的差值 dx 和 dy。
- 根据两点间距离公式计算道路长度，并乘以 2 后累加到 sum 中。
计算总时间：
- 将总路程 sum 除以 1000 转换为千米，再除以铲雪速度 20 千米/时，乘以 60 得到总分钟数，用 round 函数取整。
- 计算小时数 hours 和剩余分钟数 minutes。
使用 printf 按照指定格式输出小时和分钟，程序结束。