限制条件:
1<=L<=106
1<=n<=106
0<=xi<=L
样例:
输入
L=10
n=3
x={2,6,7}
输出
min=4{左、右、右}
max=8{右、右、右}
解题分析:
对于最短时间,我们可以考虑当所有蚂蚁都向最近的端点移动时,这时不会发生两只蚂蚁相碰的情况,也就是时间最短的情况。
对于最长时间,你也许会想蚂蚁有向左向右两种情况,相碰之后又向相反的方向移动,n只蚂蚁就有2n种可能,要考虑的情况就会特别多,而随n的增大急剧增加。但你仔细想一下两只蚂蚁相遇时的情况(如下图)会发现,由于相遇时相互反向移动且速度相同,我们可以认为是依原方向移动。
如果你是高中生,一定会立马想到物理学中的动能定理……
#include<iostream>
#include<algorithm>
constint L = 10;
constint n = 3;
constint x[n] = {2,6,7};
intmain() {
int min, max;
min = max = 0;
int minX, maxX;
for(inti=0; i<n; i++) {
minX = x[i]<L-x[i]?x[i]:L-x[i];
min = minX>=min?minX:min;
maxX = x[i]>(L-x[i])?x[i]:L-x[i];
max= maxX>max ? maxX : max;
}
cout<<min<<" "<<max<<endl;
return 0;
}