2020牛客暑期多校第五场

2020牛客暑期多校第六场

Codeforces: Educational Codeforces Round 92

AtCoder: M-SOLUTIONS Programming Contest 2020

AtCoder:

Air Safety

具体见本周推荐.

Codeforces: Educational Codeforces Round 92

Codeforces: Educational Codeforces Round 92

AtCoder: M-SOLUTIONS Programming Contest 2020

AtCoder:

Air Safety

题意:给出一个二维平面上一些飞机的坐标和它们飞行的方向(上下左右之一),飞机会沿着飞行方向一直移动.问最近的一次碰撞将会发生在什么时候.

tag: set

题解:分类讨论,首先是上下碰与左右碰的情况,以及两架飞机在y=x+a或y=a-x上时,发生的四种直角碰撞.对于单一的碰撞方式,例如上下碰,可以先把所有向下走的飞机的纵坐标扔到set里,然后枚举所有向上走的飞机,求它的纵坐标在set里的前驱,算一个答案并维护最小值即可.不用set应该也可以,只不过判断时可能麻烦一点.

comment:set的良好练手题.之前看一篇辣鸡博客说set的lower_bound是求小于等于一个值的最后一个元素的,实际上人家是求大于等于一个值的第一个元素的,也就是lower_bound返回的迭代器再往前一个才是前驱,导致浪费了很多调试的时间.