题目链接

题意：

　　蚂蚁在一个杆子上行走，每个蚂蚁有开始的位置，且速度都是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 ;

}

巴特西

Ants，小小思维题。

题目链接

题意：

题目分析：

最新文章

热门文章