题目链接

题意:

  蚂蚁在一个杆子上行走,每个蚂蚁有开始的位置,且速度都是1,如果蚂蚁“相撞”就会各自回头,以原速度继续行走,走到杆子边上就会掉下去,请问最快都掉下去的时间和最慢都掉下去的时间。

题目分析:

  读完题后,我们就想一想一些情况吧,其实最快非常显然,啥都不用想,让他们都向着容易掉下去的方向走,最后一个掉下去的就是要求的时间,简单想一下,如果这样的话他们也不会相撞(因为靠左的要向左走,靠右的要向右走,所有以中间为分界线,左边向左,右边向右,就不会相撞)。然后记录一下时间就好了。

  那么最大呢?最大就无法避免相撞的问题了,但是,这一题相撞之后所给的描述是“各自回头”,这个各自回头造成我们不好追踪某个蚂蚁,也不好确定这个蚂蚁到达做了什么贡献,所有我们进行一个巧妙的转换:我们把“各自回头”改为“互相穿过”,这其实是没有区别的,为什么呢,因为蚂蚁都是一样的,相撞之后他对面回头了,就等级与你穿过去了,这样一改,题目就显得异常简单:找每个蚂蚁掉下去的最大,然后在其中取最大(其实最小也可以这样思考)。

  好简单,其实我们还可以类比一下:如果改为一些质量相等的小球以不同的速度在无摩擦的杆子上运动,且碰撞为弹性碰撞,每个小球的初始速度不同,求最快和最慢掉下去的时间。其实是一样的。也是碰撞相当于穿过(弹性碰撞是什么应该知道吧,就是碰撞完交换速度)。最后,放一下代码(里面的处理方法可能不同,但原理类似)。

#include <cstdio>
#include <string>
using namespace std;
const int maxn=+;
int a[maxn];
int main(){
int t;
scanf("%d",&t);
for(int jsjs=;jsjs<=t;jsjs++){
int c,n;
scanf("%d%d",&c,&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int ans=;
int jl1=;
int jl2=;
for(int i=;i<=n;i++){
ans=max(ans,min(a[i],c-a[i]));
if(a[i]<a[jl1])
jl1=i;
if(a[i]>a[jl2])
jl2=i;
}
printf("%d %d\n",ans,a[jl2]-a[jl1]+max(a[jl1],c-a[jl2]));
}
return ;
}
05-21 08:24