OJ万题详解––木板上的蚂蚁(C++详解)

题目

题目描述

有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

输入格式

第一行输入三个正整数n，a，b，分别表示木板的长度，初始向左移动蚂蚁的数量和向右移动蚂蚁的数量

第二行输入a个空格分开的非负整数，分别表示向左移动蚂蚁的初始位置

第二行输入b个空格分开的非负整数，分别表示向右移动蚂蚁的初始位置

输出格式

输出只有一个整数，表示最后一只蚂蚁从木板上掉下来的时刻。

样例

样例输入 1

4 2 2
4 3
1 0
           

样例输出 1

4
           

样例解释 1

如上图所示：

-下标 0 处的蚂蚁命名为 A 并向右移动。

-下标 1 处的蚂蚁命名为 B 并向右移动。

-下标 3 处的蚂蚁命名为 C 并向左移动。

-下标 4 处的蚂蚁命名为 D 并向左移动。

请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。

样例输入 2

7 0 8
0 1 2 3 4 5 6 7
           

样例输出 2

7
           

样例解释 2

所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

样例输入 3

7 8 0
0 1 2 3 4 5 6 7
           

样例输出 3

7
           

样例解释 3

所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。

样例输入 4

9 1 1
5
4
           

样例输出 4

复制         5
           

样例解释 4

t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。

数据范围与提示

数据范围：

1 <= n <= 10^4

0 <= a <= n + 1

0 <= left[i] <= n

0 <=b <= n + 1

0 <= right[i] <= n

1 <= a + b <= n + 1

left 和 right 中的所有值都是唯一的，并且每个值只能出现在二者之一 中。

分析

这道题看似很绕，蚂蚁不停地往返往返，光看着样例解释就让人头晕眼花。

但是这一道题实则不难，我们通过数学思想可以得知，如果两只蚂蚁相遇了，就不用讨论他们何时相遇，只用把他们的身份互换了就行了，有了这个思路，我们很快就能知道，花费的时间最大其实就是要走的距离最大，就只要算出蚂蚁距离端点的最大值就行了

for(int i=1;i<=l;i++){
    cin>>a[i];
    maxl=maxl<a[i]?a[i]:maxl;
}
           

这一块代码是计算往左走蚂蚁的最大值。

for(int i=1;i<=r;i++){
    cin>>b[i];
    maxr=maxr<s-b[i]?s-b[i]:maxr;
}
           

 这一块就是计算向右走蚂蚁的 最大值。

然后接着输出就可以了

接下来就是参考代码

参考代码

#include<bits/stdc++.h>
using namespace std;
long long s,l,r,maxl=INT_MIN;
long long maxr=INT_MIN,a[10005],b[10005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>s>>l>>r;
	for(int i=1;i<=l;i++){
		cin>>a[i];
		maxl=maxl<a[i]?a[i]:maxl;
	}
	for(int i=1;i<=r;i++){
		cin>>b[i];
		maxr=maxr<s-b[i]?s-b[i]:maxr;
	}
	cout<<max(maxr,maxl)<<endl;
	return 0;
}