# 853.Car Fleet

**853.Car Fleet**

> N辆车沿着一条车道驶向位于 target 英里之外的共同目的地。 每辆车 i 以恒定的速度 speed\[i] （英里/小时），从初始位置 position\[i] （英里） 沿车道驶向目的地。 一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。 此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。 车队 是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。 即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。 会有多少车队到达目的地?

示例：

```
输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
解释：
从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。
```

提示：

```
0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
所有车的初始位置各不相同。
```

方法： 一辆车追上另一辆车的状况是，后面的车距离目标更远，但到达目的时间不超过前面的车。

* 理论情况是所有车都在匀速行驶，但如果前面的车追上了更前面的车，那么前面的车速度就会变。此时追上的车可以视为消失了，那么只需要比较后面的车与前前面的车。以此类推。
* 从最末尾一辆车计算，初始总车队即为车数，随着追上逐渐减少。
* 创建了一个向量保存车队到达目的地时间。创建了一个函数，用来排序车队和相应到达时间。
* 然后从末尾车开始比较，如果追上了前面的车，则到达时间也与前面的车相等，车队总数减1，遍历一边车队。
* 得到最终结果。

```
class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int N=position.size();
        if(!N) return 0;
        vector<float>time(N,0);
        for(int i=0;i<N;i++)
            time[i]=(target-position[i]+0.0)/speed[i];
        ordered(position,time);
        int result=N;
        for(int i=N-1;i>0;i--)
        {
            if(time[i] >= time[i-1])
            {
                time[i-1]=time[i];
                result--;
        }
        }
        return result;

    }
private:
    int ordered(vector<int> &position,vector<float> &time)
    {
        int N=position.size();
        for(int i=0 ; i<N;i++)
            for(int j=i+1;j<N;j++)
            {
                float temp;
                int tempn;
                if(position[i]>position[j])
                {
                    tempn=position[i];
                    position[i]=position[j];
                    position[j]=tempn;
                    temp=time[i];
                    time[i]=time[j];
                    time[j]=temp;
                }
            }
        return 0;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/853.car_fleet.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.