首页 > 技术文章 > ICPC2020上海 D题 Walker

Creed-qwq 2020-12-19 16:53 原文

Pro:
https://codeforces.com/gym/102900/problem/D

给定一条[0,n]的路

有两个人分别在\(p_1,p_2\)位置

速度分别为\(v_1,v_2\)

同时出发,任意游走

问最短多久遍历整条路

Sol:
贪心+讨论

发现一共三种情况

1.一个人不动,另一个跑全程

2.两个人分别往对方的方向走,直到边界

3.两个人分别负责一段区间,左边的人负责左边的一段区间,右边的人负责右边的一段区间。
这种情况只需要找最优分界点即可,这显然是个凹函数,三分即可

推荐阅读