蚂蚁【A001】

【1005】出自附中练习场，其他编号（1005）【难度A】—————————————————————————————————————————————————————————————————————————————————————————————

【题目要求】有一群蚂蚁在一根水平放置的长为L cm的木棍上行走，并且每只蚂蚁的速度都固定为1 cm/s。当一只蚂蚁走到木棍的两端时就不幸地掉落了，当两只蚂蚁相碰时，它们就分别反向行走，并假设忽略相碰的时间。现在我们已知木棍的长度L，蚂蚁的只数N和每只蚂蚁在木棍上的初始位置Ai（以木棍一段为坐标原点0，另一端为木棍长度L），但是蚂蚁可以随机的选择它们的初始行走方向。你的任务是求出在所给定条件下，对蚂蚁行走方向任意的所有情况下，求出所有蚂蚁都从木棍上掉落的最早时间和最晚时间。

【输入要求】第一行两个正整数是L（木棍长度）和N（蚂蚁只数），接着一行是N个正整数Ai（1<=i<=N，0<=Ai<=L）。(1<=L<=1000，1<=N<=1000)

【输出要求】一行包括两个数用一个空格分隔，分别表示最早时间和最晚时间。

【输入示例】

10 3
2 6 7

【输出示例】

4 8

【解析】此题难度很低，但有一点必须理解，就是两只蚂蚁相撞之后什么也没发生，因为蚂蚁并不区分，不同蚂蚁掉下去并不影响结果，所以我们可以加入一些贪心算法：让最靠近某一木棍端点的蚂蚁向对面爬行，就是最晚时间，最早时间就找在中间的蚂蚁，向近的端点爬行。

【代码】

#include<iostream>

using namespace std;

int main()
{
    int i,l,n,a[10000],min[10000],e,r;
    cin>>l>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<n;i++)
    {
        if(a[i]<=l/2)
            min[i]=a[i];
        else
            min[i]=l-a[i];
    }
    e=min[0];
    for(i=0;i<n;i++)
    {
       if(min[i]>e)
         e=min[i];
    }
    r=min[0];
    for(i=0;i<n;i++)
    {
       if(min[i]<r)
         r=min[i];
    }
    cout<<e<<" "<<l-r;
    //system("pause");
    return 0;
}

【注】此题已AC，代码很简单不用解释了吧。