CF1501A Alexey and Train 题解
Content
一列火车从 \(0\) 时刻开始从 \(1\) 号站出发,要经过 \(n\) 个站,第 \(i\) 个站的期望到达时间和离开时间分别为 \(a_i\) 和 \(b_i\),并且还有一个实际延迟时间 \(tm_i\)。具体地,第 \(i\) 个站的实际到达时间为 \(a_i-b_{i-1}+tm_i\) 时刻,当且仅当以下两种条件同时符合时离开车站:
- 火车已经在这个车站停靠了 \(\left\lceil\dfrac{b_i-a_i}{2}\right\rceil\) 个时刻。
- 当前时刻 \(\geqslant b_i\)。
求这列火车到达 \(n\) 号站的时刻。
数据范围:\(t\) 组数据,\(1\leqslant t\leqslant 100\),\(1\leqslant n\leqslant 100\),\(1\leqslant a_i<b_i\leqslant 10^6\),\(0\leqslant tm_i\leqslant 10^6\)。
Solution
事实上,读懂题面之后,这道题目是不难的。我们只需要做些简单的模拟,从 \(1\) 到 \(n\) 更新 \(a_i,b_i\) 为增加延迟时间之后的时刻即可。具体地,我们先把当前站的期望到站时间和离开时间 \(a_i,b_i\) 存储一下,设为 \(prea,preb\),并且将前一个站的离开时间也存储一下,设为 \(ppreb\),然后我们新的 \(a_i\) 在题目中已有公式给出,就等于 \(preb+a_i-ppreb+tm_i\),新的 \(b_i\) 由题目中的条件可知为 \(\max\{a_i+\left\lceil\dfrac{b_i-prea}{2}\right\rceil,b_i\}\)。
存储 \(prea,preb\) 的目的想必大家都很明白,因为后面 \(a_i,b_i\) 都会改变,直接拿 \(a_i,b_i\) 来代入上面的公式肯定会出错。至于 \(ppreb\) 就更不用说了。
具体看代码实现。
Code
int n, a[107], b[107], tim[107], preb, ppreb;
int main() {
MT {
n = Rint;
F(i, 1, n) a[i] = Rint, b[i] = Rint;
F(i, 1, n) tim[i] = Rint;
preb = ppreb = b[0];
F(i, 1, n) {
int prea = a[i];
a[i] = (preb + a[i] - ppreb + tim[i]);
ppreb = b[i];
b[i] = max(a[i] + (int)ceil((b[i] - prea) / 2.0), b[i]);
preb = b[i];
}
printf("%d\n", a[n]);
}
return 0;
}
最新文章
- Mongodb Manual阅读笔记:CH3 数据模型(Data Models)
- Js动态获取iframe子页面的高度总结
- 2015弱校联盟(1) - E. Rectangle
- js:语言精髓笔记7----原型继承
- 20145227《Java程序设计》第10周学习总结
- ajax对一些没有接口的数据进行分析和添加方法
- poj3254
- [Oracle]Sqlplus连接成功,但pl/sql连接不成功,提示“ora-12145:无法解析指定的连接标识符”
- JavaScript快速入门(五)——表达式运算
- ASP.NET MVC---自定义HtmlHelper方法
- 生肖年(switch练习)
- C++中指向类的指针
- Unity --- 设置选择的图片的格式
- esp8266(2) 智能配置
- img2html实现将图片转换成网页
- CodeChef KILLKTH Killjee and k-th letter
- jquery 实现iframe 自适应高度
- jsp 中 , jq 获取当前所点击的 select 的 id 值的注意事项
- 基础篇:3.2)规范化:3d零件建模
- npm报错npm ERR! A complete log of this run can be found in: npm ERR! C:\Users\Administrator\AppData\Roaming\npm-cache\_logs\2018-03-15T01_48_14_769Z-debug.log