LeetCode 853. Car Fleet

傳送門

題目分析

N

cars are going to the same destination along a one lane road. The destination is

target

miles away.

Each car

i

has a constant speed

speed[i]

(in miles per hour), and initial position

position[i]

miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored - they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: target = , position = [,,,,], speed = [,,,,]
Output: 
Explanation:
The cars starting at  and  become a fleet, meeting each other at 
The car starting at  doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at  and  become a fleet, meeting each other at 
Note that no other cars meet these fleets before the destination, so the answer is 
           

Note:

1. 0 <= N <= 10 ^ 4

2. 0 < target <= 10 ^ 6

3. 0 < speed[i] <= 10 ^ 6

4. 0 <= position[i] < target

5. All initial positions are different.

說實話，這道題挺讓我頭疼的，題目意思有些迷迷糊糊，最終在百度翻譯的幫助下還是順利了解了題意，給你一個目的地，幾輛車的初始位置和速度，判斷最後會剩幾個

車隊

，相遇的車變成一個。

思考

确實挺頭疼，首先可以确定是從離終點較遠的位置開始，一個一個向起點位置逼近，兩輛車想撞的條件就是一輛車在前面并且到達結束位置的時在前的車用時較長，這樣把每輛車都和前面的車相比，如果這輛車不會和前面的相撞，那麼它就會成為下一個車隊。

代碼實作

using ll = long long;

struct Node {
    int position;
    int speed;
    double use_time;
    friend bool operator<(const Node &a, const Node &b) {
        // 怎麼排序
        return a.position >= b.position;
    }

    friend bool operator==(const Node &a, const Node &b) {
        // 實際上不能用==，不滿足重寫==的3個條件，為了友善先這麼寫吧
        // a就是前面的車，b是後面的
        return a.position >= b.position && a.use_time >= b.use_time;
    }
};

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        if (position.size() == ) {
            return ;
        }
        // 直接模拟需要從前向後模拟吧，如果一輛車可以
        int size = position.size();
        vector<Node> nodes;
        Node n;
        for (int i = ; i < size; ++i) {
            n.position = position[i];
            n.speed = speed[i];
            n.use_time =  * (target - n.position) / n.speed;
            nodes.push_back(n);
        }
        sort(nodes.begin(), nodes.end());
        // 開始判斷能否追上
        int result = ;
        Node old = nodes[];
        for (int i = ; i < size; ++i) {
            // 不能在一個車隊中
            if (!(old == nodes[i])) {
                old = nodes[i];
                ++result;
            }
        }

        return result;
    }
};
           

感想

。。。