|
试题描述
|
|
有N只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反向爬回去。对于每只蚂蚁，我们知道它距离杆子左端的距离Xi，但不知道它当前的朝向。请计算所有蚂蚁都从竿子上掉落所需的最短时间和最长时间。 |
|
输入
|
|
多组测试数据。
每组数据包含两行，第一行包含2个整数N、L。（1≤N，L≤10^6）。 接下来一行有N个整数Xi（0≤Xi≤L），Xi表示第i只蚂蚁距离竿子左端点的距离。 |
|
输出
|
|
每组数据输出两行，格式见样例。每两组数据之间输出一个换行。
|
|
输入示例
|
|
10 3
2 6 7 |
|
输出示例
|
|
min = 4
max = 8 |
这道题看起来很复杂，还有蚂蚁的转向。但其实仔细分析一下，就能发现其实不用考虑转向。如果不考虑蚂蚁本身的差异，两只蚂蚁碰到后均转向这种情况，可以看成碰到后继续走，这样就好办了。最大值取离端点最近的蚂蚁，此时这只蚂蚁向里爬；最小值取离终点最近的蚂蚁，此时蚂蚁向中点爬。
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 int a[100001]; 5 int main() 6 { 7 int n,L,i; 8 scanf("%d%d",&n,&L); 9 int t,min=1000000,minl=1000000,minr=1000000,mid=n/2,minn=1000000; 10 for(i=1;i<=L;i++) 11 { 12 scanf("%d",&a[i]); 13 if(abs(mid-a[i])<abs(minn-mid)) minn=a[i]; 14 minl=a[i]; 15 minr=n-a[i]; 16 if(minl<min) min=minl; 17 if(minr<min) min=minr; 18 } 19 cout<<"min = "<<n-minn<<endl; 20 cout<<"max = "<<n-min; 21 return 0; 22 }
原文：http://www.cnblogs.com/YXY-1211/p/4982930.html
