C++刷LeetCode（1503. 所有蚂蚁掉下来前的最后一刻）【数学】【分情况讨论】

糖逗

题目描述：

1. 有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
   
2. 
   
3. 当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。
   
4. 
   
5. 而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
   
6. 
   
7. 给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13.  
    
14. 
    
15. 输入：n = 4, left = [4,3], right = [0,1]
    
16. 输出：4
    
17. 解释：如上图所示：
    
18. -下标 0 处的蚂蚁命名为 A 并向右移动。
    
19. -下标 1 处的蚂蚁命名为 B 并向右移动。
    
20. -下标 3 处的蚂蚁命名为 C 并向左移动。
    
21. -下标 4 处的蚂蚁命名为 D 并向左移动。
    
22. 请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。
    
23. 示例 2：
    
24. 
    
25. 
    
26. 
    
27. 输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7]
    
28. 输出：7
    
29. 解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。
    
30. 示例 3：
    
31. 
    
32. 
    
33. 
    
34. 输入：n = 7, left = [0,1,2,3,4,5,6,7], right = []
    
35. 输出：7
    
36. 解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
    
37. 示例 4：
    
38. 
    
39. 输入：n = 9, left = [5], right = [4]
    
40. 输出：5
    
41. 解释：t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。
    
42. 示例 5：
    
43. 
    
44. 输入：n = 6, left = [6], right = [0]
    
45. 输出：6
    
46.  
    
47. 
    
48. 提示：
    
49. 
    
50. 1 <= n <= 10^4
    
51. 0 <= left.length <= n + 1
    
52. 0 <= left[i] <= n
    
53. 0 <= right.length <= n + 1
    
54. 0 <= right[i] <= n
    
55. 1 <= left.length + right.length <= n + 1
    
56. left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。
    
57. 
    
58. 来源：力扣（LeetCode）
    
59. 链接：https://leetcode-cn.com/problems/last-moment-before-all-ants-fall-out-of-a-plank
    
60. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int getLastMoment(int n, vector<int>& left, vector<int>& right) {
   
4.         sort(left.begin(), left.end());
   
5.         sort(right.begin(), right.end());
   
6.         int len1 = left.size(), len2 = right.size();
   
7.         if(len1 == 0 && len2 == 0)return 0;
   
8.         else if(len1 == 0) return n - right[0];
   
9.         else if(len2 == 0) return left[len1 - 1];
   
10. 
    
11.         int temp1 = right[0], temp2 = left[len1 - 1];
    
12.         int res = 0;
    
13.         if(temp1 < temp2){
    
14.             if(temp2 - temp1 == 1){
    
15.                 int time1 = n - temp2;
    
16.                 int time2 = temp1;
    
17.                 res = max(time1, time2) + 1;
    
18.             }else if((temp2 - temp1) % 2 == 0){
    
19.                 int mid = temp1 + (temp2 - temp1)/2;
    
20.                 int time1 = mid - temp1 + mid;
    
21.                 int time2 = temp2 - mid + n - mid;
    
22.                 res = max(time1, time2);
    
23.             }else{
    
24.                 int mid1 = temp1 + (temp2 - temp1)/2;
    
25.                 int mid2 = mid1 + 1;
    
26.                 int time1 = mid1 - temp1 + mid1;
    
27.                 int time2 = temp2 - mid2 + n - mid2;
    
28.                 res = max(time1, time2) + 1;
    
29.             }
    
30.         }else if(temp1 == temp2){
    
31.             res = max(temp1, n - temp1);
    
32.         }else if(temp1 > temp2){
    
33.             if(temp1 - temp2 == 1){
    
34.                 res = max(temp1, n - temp2) + 1;
    
35.             }else{
    
36.                 res = max(n - temp1, temp2);
    
37.             }
    
38.         }
    
39.         return res;
    
40.     }
    
41. };

复制代码