leetcode853 车队

题目

车队

分析

题意：几辆车同时出发，每辆车的初始位置不一样，速度也不一样，一开始位置就落后的车不能超过前面的车，只能组成车队，问穿过终点时，有几个车队。

每辆车的初始位置不一样，速度不一样，那么到达终点所需的时间也存在差别。如果位置在后面的车到达终点所花的时间比在前面的车花的时间还要少，那么这两个车在途中一定能相遇组成车队。

所以我们把车按照初始位置排序，在对时间离散化一次就能得到解。

代码

struct MyNode{
    double position;
    double time;

    MyNode(int p, double t) {
        position = p;
        time = t;
    }
};

class Solution {
private:
    static bool cmp(const MyNode& n1, const MyNode& n2) {
        return n1.position > n2.position;
    }
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        if (position.empty()) {
            return 0;
        }

        vector<MyNode> vec;
        for (int i = 0; i < position.size(); i++) {
            vec.push_back(MyNode(position[i], (double)(target - position[i]) / (double)speed[i]));
        }

        sort(vec.begin(), vec.end(), cmp);

        int res = 1;

        for (int i = 1; i < vec.size(); i++) {
            if (vec[i].time > vec[i - 1].time) {
                res++;
            } else {
                vec[i].time = vec[i - 1].time;
            }
        }

        return res;
    }
};