JZX轻语：简

LeetCode 853 - 车队

发表于2024年05月16日

#排序 #TODO

首先对所有的车按位置从大到小排序，以获得有序的位置信息。不难得知，每个车队的速度都以车头(即距离更大者)为准，也即车和车队之间的比较只要以车头为准。因此，可以使用两个变量分别维护当前所处理车队的车头起始位置和速度，按位置顺序遍历所有的车辆，如果当前车辆能在target之前赶上该车队(的车队)，则将其合并在同一个车队中；否则(要么速度不够，要么追上时已经在target之后了)，以该车作为车头新建一个车队即可，并跳至新车队的处理，而旧车队后面不会有其他车跟上了(因为后面的车追上去后，只能以新车队的车头的速度继续前进，而这个车头本来就追不上旧车队)。

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        car_infos = sorted(zip(position, speed), key=lambda item: -item[0])  # 按距离倒序排序
        cur_fleet_head_pos, cur_fleet_head_speed = car_infos[0]
        ans = 1
        for i in range(1, len(car_infos)):
            pos, spd = car_infos[i]
            if (cur_fleet_head_speed >= spd
                    or (cur_fleet_head_pos - pos) / (spd - cur_fleet_head_speed) > (target - cur_fleet_head_pos) / cur_fleet_head_speed):  # 追不上现有车头
                ans += 1
                cur_fleet_head_pos = pos
                cur_fleet_head_speed = spd
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/car-fleet/