escape on the train求助

从第一个例子来看，我认为是可以呆在原地不动的，因为两个乘客距离出口的距离都是101，假如不能原地不动，那么肯定有一个乘客需要浪费两步让第一个乘客先出去。那答案是103。结果是102，说明第二个乘客在等第一个乘客出去的时候是呆在原地的。他的解释里也说（1-0）+（100-0）= 101，  （2-1）+（100-0）= 101，

1. 
   
2. /******************************************************************************
   
3. 
   
4.                               Online C++ Compiler.
   
5.                Code, Compile, Run and Debug C++ program online.
   
6. Write your code in this editor and press "Run" button to compile and execute it.
   
7. 
   
8. *******************************************************************************/
   
9. 
   
10. #include <iostream>
    
11. #include <vector>
    
12. #include <algorithm>
    
13. using namespace std;
    
14. 
    
15. int escape(vector<vector<int>> passengers)
    
16. {
    
17.     sort(passengers.begin()+1, passengers.end(), [&](auto& a, auto& b){return abs(passengers[0][1]-a[0])+a[1]<abs(passengers[0][1]-b[0])+b[1];});
    
18.     int res = 0;
    
19.     for(int i=1; i<passengers.size(); ++i)
    
20.         res = max(abs(passengers[i][0] - passengers[0][1]) + passengers[i][1], res + 1);
    
21.     return res;
    
22. }
    
23. 
    
24. int main()
    
25. {
    
26.     cout << escape({
    
27.         {2,0},
    
28.         {0,100},
    
29.         {2,100}
    
30.     }) << endl;
    
31.     cout << escape({
    
32.         {2,1},
    
33.         {1,0},
    
34.         {1,1}
    
35.     }) << endl;
    
36.     cout << escape({
    
37.         {1,1},
    
38.         {1,10}
    
39.     }) << endl;
    
40.     return 0;
    
41. }
    
42. 
    
43. [i][i][i][i]

复制代码

[/i][/i][/i][/i]

[i][i][i]时间复杂度nlg（n）
求大米

[/i][/i][/i]