USACO2014 铜组第二题

题目描述

贝茜（Bessie）这头牛正在参加一场冬季越野滑雪比赛。比赛的赛道是笔直的，她一开始的速度是 1 米/秒。然而，随着比赛进行，贝茜会逐渐疲劳，开始减速：

• 每次减速后，她的速度会降低：第一次减速后，速度变为 1/2 米/秒；第二次减速后，速度变为 1/3 米/秒；第三次减速后，速度变为 1/4 米/秒，以此类推。

你会得到一系列标记贝茜减速时刻的事件，事件分为两种类型：

• 时间事件（T x）：表示贝茜在比赛进行到第 x 秒时减速。
• 距离事件（D x）：表示贝茜在滑行到距离起点 x 米时减速。

给定 N 个这样的事件（1 ≤ N ≤ 10,000），请计算贝茜滑行 1 千米（1000 米） 所需的总时间（单位：秒）。最终结果四舍五入到最近的整数（0.5 及以上向上取整）。

输入格式

• 第 1 行：整数 N（事件的数量）。
• 第 2 至 N+1 行：每行是一个事件，格式为 T x 或 D x，其中 x 是整数。保证所有事件发生时，贝茜尚未完成 1 千米的滑行。事件可能不是按时间或距离顺序给出的，也可能存在同时发生的事件（此时贝茜会一次性多次减速）。

输出格式

输出 1 行，为贝茜滑行 1 千米所需的总时间（四舍五入到最近整数）。

样例输入

2
T 30
D 10

输入详情：
贝茜会在比赛进行到 30 秒时减速，以及在滑行到 10 米距离时减速。

样例输出

2970

输出详情：

1. 贝茜以 1 米/秒 滑行前 10 米，耗时 10 秒。
2. 第一次减速后，速度变为 1/2 米/秒。她以该速度滑行到 30 秒标记点，又滑行了 30 - 10 = 20 秒，滑行距离为 (1/2) * 20 = 10 米（累计滑行 20 米）。此时触发时间事件，再次减速，速度变为 1/3 米/秒。
3. 剩余距离：1000 - 20 = 980 米，以 1/3 米/秒 滑行，耗时 980 * 3 = 2940 秒。
4. 总时间：10 + 20 + 2940 = 2970 秒。

约束条件

• 事件数量 N 满足 1 ≤ N ≤ 10,000。
• 所有事件保证在贝茜完成 1 千米前发生。
• 输入的事件可能无序，且可能存在同时发生的情况（需按规则处理多次减速）。