#P3431. [Usaco2014 Jan]Bessie Slows Down

    ID: 2625 传统题 1000ms 512MiB 尝试: 209 已通过: 96 难度: 3 上传者: 标签>难度分类普及模拟与实现技巧事件驱动模拟离线与分治事件排序添加哨兵CF1300Silver

[Usaco2014 Jan]Bessie Slows Down

[USACO14JAN] Bessie Slows Down S

题目描述

贝西参加冬季运动会的越野滑雪比赛,赛道全长 10001000 米。她从起点出发时速度为每秒 11 米。发生第 kk 次减速事件后,她的速度变为每秒 1k+1\frac{1}{k+1} 米。

有两类减速事件。一类在出发后达到指定时间时发生,另一类在滑到距起点指定距离时发生。事件不一定按发生顺序给出。同一时刻发生的每条记录都各算一次减速。

求贝西到达终点所需的总时间。答案四舍五入到最接近的整数秒,恰好是半秒时向上取整。

输入格式

第一行一个整数 NN,表示减速事件数,1≤N≤100001\le N\le 10000。

接下来 NN 行,每行给出一个大写字母和一个整数。

  • T x 表示出发后第 xx 秒发生减速,1≤x≤1071\le x\le 10^7。这类事件在到达终点之前发生。
  • D x 表示滑到距起点 xx 米处时发生减速,1≤x≤10001\le x\le 1000。若 x=1000x=1000,该记录对到达时间没有影响。

输出格式

输出一个整数,表示按上述规则取整后的总时间(秒)。

样例 #1

2
T 30
D 10
2970

样例解释

贝西先以每秒 11 米的速度滑过 1010 米,用时 1010 秒。到达 1010 米处减速后,她以每秒 12\frac{1}{2} 米的速度再滑 2020 秒。此时她滑了 2020 米,并在第 3030 秒再次减速。剩下的 980980 米以每秒 13\frac{1}{3} 米的速度滑完,用时 29402940 秒。总时间为 10+20+2940=297010+20+2940=2970 秒。