D - Pick Up
基本信息
题目出处 | 2019 陕西省大学生程序设计竞赛 |
队伍通过率 | 4/111 (3.6%) |
题解
首先计算 BaoBao 直接去商场的时间。接下来计算 DreamGrid 接 BaoBao 去商场的最短时间。
记
因此讨论 BaoBao 和 DreamGrid 谁先到达
- 如果 BaoBao 先到达
点,那么接下来他直接往 点走,等 DreamGrid 追上他。因为 DreamGrid 完全没有绕路,所以到达商场的时间就是 DreamGrid 直接去商场的时间。 - 如果 DreamGrid 先到达
点,由于 DreamGrid 速度比 BaoBao 快,所以越早接到 BaoBao 越好。可以发现,DreamGrid 先到 再到 ,和他直接去 走的距离是一样的。因此 DreamGrid 到达 点之后应该继续往 点走,直到接上 BaoBao,这样就能最快接到 BaoBao。最后两个人再一起去商场。
复杂度
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|