leetcode：1094. 拼车（贪心）

题目：

分析：

看到一半题，还觉得是紫书上的那个难题，可吓坏我了。
–可否：这就简单了。web

代码：

void Qsort(vector<vector<int>> &arr, int low, int high){
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = arr[low][1];
    while (true)
    {
        /*从左向右找比key大的值*/
        while (arr[++i][1] < key)
        {
            if (i == high){
                break;
            }
        }
        /*从右向左找比key小的值*/
        while (arr[--j][1] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交换i,j对应的值*/
        int temp = arr[i][0];
        arr[i][0] = arr[j][0];
        arr[j][0] = temp;
        temp = arr[i][1];
        arr[i][1] = arr[j][1];
        arr[j][1] = temp;
        temp = arr[i][2];
        arr[i][2] = arr[j][2];
        arr[j][2] = temp;
    }
    /*中枢值与j对应值交换*/
    int temp = arr[low][0];
    arr[low][0] = arr[j][0];
    arr[j][0] = temp;
    temp = arr[low][1];
    arr[low][1] = arr[j][1];
    arr[j][1] = temp;
    temp = arr[low][2];
    arr[low][2] = arr[j][2];
    arr[j][2] = temp;
    Qsort(arr, low, j - 1);
    Qsort(arr, j + 1, high);
}
int main()
{
 vector<vector<int>> vv;
 int cap;
 Qsort(arr,0,vv.size()-1);
 int A[vv.size()];
 memset(A,0,sizeof(A));
 int all=0;
 int k=0;
 for(int i=0;i<=1000;i++)
 {
  if(k==vv.size()) break; 
  //车上总人数 先下车 
  all=all-A[i];
  while(vv[k][1]==i)
  {//有无上车
   //到达位置的下车人数 增长 
  A[vv[k][2]]+=vv[k][0];
    all=all+vv[k][0];
    if(all>cap) return false;
   k++;
            if(k==vv.size()) break; 
  }
  }  
 return true;
}

有坑：

我拉低了经过率
不是每一个车站都有人上，但没人上的可能有人下，不能直接vv.size个循环。svg

同一上车的会给多个信息，由于下车不一样。spa