当前位置: 首页 > news >正文

滑雪

解题思路

问题分析

这是一个模拟贝西滑雪过程中遇到失误导致速度变化的问题。贝西初始速度为1米/秒,每次失误后速度变为1/(k+1)米/秒(k为失误次数)。需要计算她完成1000米滑雪所需的时间。

关键点

  1. 两种失误类型

    • 时间失误(T):在特定时间点发生
    • 距离失误(D):在特定位置发生
  2. 处理顺序:需要按照实际发生的顺序处理失误(哪个先发生就先处理哪个)

  3. 速度变化:每处理一个失误,速度就会下降一次

算法思路

使用两个优先队列分别存储时间失误和距离失误,按照发生顺序(时间或位置)从小到大处理。在每一步中:

  • 计算下一个时间失误和下一个距离失误哪个先发生
  • 处理先发生的失误,更新当前位置和时间
  • 调整速度(增加失误次数k)
  • 最后处理剩余距离

代码注释

#include <bits/stdc++.h>
using namespace std;int n;
// 使用小顶堆存储时间失误和距离失误,确保按顺序处理
priority_queue<int, vector<int>, greater<int>> T, D;int main() {cin >> n;char opt;int x;for (int i = 1; i <= n; i++) {cin >> opt >> x;if (opt == 'T') T.push(x); // 时间失误加入T队列else D.push(x); // 距离失误加入D队列}double nowS = 0; // 当前行驶距离(米)double nowT = 0; // 当前所耗时间(秒)int k = 1;  // 当前失误次数double v = 1.0; // 当前速度(米/秒)// 循环直到到达终点或没有更多失误while(nowS < 1000){if(T.empty() && D.empty()) break; // 后面没失误了,退出循环double t1 = 1e18, d1, t2, d2 = 1e18;// 计算下一个时间失误需要的时间和距离if(!T.empty()){t1 = T.top() - nowT; // 到达下一个时间失误所需时间d1 = t1 * v; // 在这段时间内行驶的距离} // 计算下一个距离失误需要的时间和距离if(!D.empty()){d2 = D.top() - nowS; // 到达下一个距离失误所需的距离t2 = d2 / v; // 行驶这段距离所需的时间}// 判断时间失误和位置失误哪个先发生if(d1 <= d2 && !T.empty()){// 时间失误先发生nowS += d1; // 更新位置nowT = T.top(); // 更新时间T.pop(); // 移除已处理的时间失误} else if(!D.empty()){// 距离失误先发生nowS = D.top(); // 更新位置nowT += t2; // 更新时间D.pop(); // 移除已处理的距离失误} else{break; // 没有更多失误}// 更新速度(增加失误次数)v = 1.0/++k;// 如果时间失误和距离失误同时发生(理论上不可能完全相等,但代码做了处理)if(d1 == d2) v = 1.0/++k; // 额外增加一次失误}// 处理剩余距离(如果没有失误了但还没到达终点)if(nowS < 1000){nowT += (1000 - nowS) / v;}// 四舍五入输出整数结果int ans = (nowT + 0.5);cout<<ans;return 0;
}

算法细节

  1. 优先队列:使用小顶堆确保按顺序处理失误
  2. 比较策略:通过计算到达下一个时间失误和距离失误所需的时间和距离,判断哪个先发生
  3. 同时发生处理:代码中考虑了时间失误和距离失误同时发生的情况(虽然概率很小)
  4. 精度处理:使用double类型保证计算精度,最后四舍五入输出整数
http://www.hskmm.com/?act=detail&tid=10999

相关文章:

  • 守序者的尊严
  • 在Ubuntu22.04平台上交叉编译针对Rv1126架构的GCC13.2.0编译器
  • 深度学习(DBBNet重参数化)
  • CAR 细胞疗法:肝癌治疗的曙光与荆棘
  • Java项目案例作业1
  • 配置Spring框架以连接SQL Server数据库
  • 这一辈子大多数日子是无聊的
  • Go 实现验证码识别
  • 跳出 AI 编程的「兔子洞」,4 个实战策略帮你解决90%的死循环
  • 用 PHP 和 Tesseract OCR 识别英文数字验证码
  • 凝望深渊时,深渊也凝望着你(黑洞与摇钱树)
  • 详细介绍:《Vuejs设计与实现》第 16 章(解析器) 中
  • spring项目部署后为什么会生成 logback-spring.xml记录
  • 【解决】Matlab函数体突然不自动缩进了
  • 202509_NBWS_logbool
  • Kubernetes权威指南-深入理解Pod Service
  • 详细介绍:jeecg-boot3.7.0对接钉钉登录(OAuth2.0)
  • C++编程软件 Dev-C++ 安装及使用流程
  • DLL植入漏洞分类与微软安全响应指南
  • 4980:拯救行动
  • java03-wxj
  • 题解:P13969 [VKOSHP 2024] Exchange and Deletion
  • 市场交易反心理特征之二:忽视热点切换的苗头
  • Linux服务器上安装配置GitLab的步骤
  • 贪心算法应用:投资组合再平衡问题详解 - 实践
  • MCP:Trae中集成Playwright 实现网页自动化测试
  • C语言中的字符、字符串及内存操作函数详细讲解
  • 06、訊息收集
  • 在Linux中设定账户密码的安全性策略
  • 精选 4 款基于 .NET 开源、功能强大的 Windows 系统优化工具,助力轻松提升 Windows 系统性能与使用体验!