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

滑雪

news 2025/9/20 20:11:11

解题思路

问题分析

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

关键点

两种失误类型：
- 时间失误（T）：在特定时间点发生
- 距离失误（D）：在特定位置发生
处理顺序：需要按照实际发生的顺序处理失误（哪个先发生就先处理哪个）
速度变化：每处理一个失误，速度就会下降一次

算法思路

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

计算下一个时间失误和下一个距离失误哪个先发生
处理先发生的失误，更新当前位置和时间
调整速度（增加失误次数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;
}