前缀和 LeetCode1094 拼车

1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105 

当前人数是由当前上车人数-当前下车人数决定的。因为from和to小于1000，所以可以使用大小为1000的数组path，表示每个点上车和下车的人数之差。 默认为0.

遍历trips：t

path[t[1]]+=t[0]；path[t[2]]-=t[0];

然后对path求前缀和，如果前缀和大于最大容量，说明超载返回false.

最后返回true。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int path[1001];
        memset(path,0,sizeof(path));
        for(int i=0;i<trips.size();i++){
            vector<int>t=trips[i];
            path[t[1]]+=t[0];
            if(path[t[1]]>capacity)return false;
            path[t[2]]-=t[0];
        }
        int s=0;
        for(int i=0;i<1001;i++){
            s+=path[i];
            if(s>capacity)return false;
        }

        return true;

    }
};