C++刷LeetCode（1503. 所有蚂蚁掉下来前的最后一刻）【数学】【分情况讨论】
题目描述：有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。
而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。
示例 1：
输入：n = 4, left = , right =
输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。
示例 2：
输入：n = 7, left = [], right =
输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。
示例 3：
输入：n = 7, left = , right = []
输出：7
解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
示例 4：
输入：n = 9, left = , right =
输出：5
解释：t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。
示例 5：
输入：n = 6, left = , right =
输出：6
提示：
1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left <= n
0 <= right.length <= n + 1
0 <= right <= n
1 <= left.length + right.length <= n + 1
left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-moment-before-all-ants-fall-out-of-a-plank
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int len1 = left.size(), len2 = right.size();
if(len1 == 0 && len2 == 0)return 0;
else if(len1 == 0) return n - right;
else if(len2 == 0) return left;
int temp1 = right, temp2 = left;
int res = 0;
if(temp1 < temp2){
if(temp2 - temp1 == 1){
int time1 = n - temp2;
int time2 = temp1;
res = max(time1, time2) + 1;
}else if((temp2 - temp1) % 2 == 0){
int mid = temp1 + (temp2 - temp1)/2;
int time1 = mid - temp1 + mid;
int time2 = temp2 - mid + n - mid;
res = max(time1, time2);
}else{
int mid1 = temp1 + (temp2 - temp1)/2;
int mid2 = mid1 + 1;
int time1 = mid1 - temp1 + mid1;
int time2 = temp2 - mid2 + n - mid2;
res = max(time1, time2) + 1;
}
}else if(temp1 == temp2){
res = max(temp1, n - temp1);
}else if(temp1 > temp2){
if(temp1 - temp2 == 1){
res = max(temp1, n - temp2) + 1;
}else{
res = max(n - temp1, temp2);
}
}
return res;
}
};
页:
[1]