Online Judge

【POJ】[1852]Ants

文章字数：490

问题描述

问题分析

智商题

n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反向爬回去。对于每只蚂蚁，我们知道它距离竿子左端的距离xi，但不知道它当前的朝向。请计算所有蚂蚁落下竿子所需的最短时间和最长时间。

似乎对照书打一遍毫无意义啊……-.-

反正是统计 就当做休息一下啦

作为《挑战程序设计竞赛》中第一道比较正规的题

刚开始想的时候对这本书的难度惊呆了-_-

感叹智商不够

然后这个就是

image.png

关键就是想到蚂蚁的运动都可以理解为单独运动的

所以求时间最短时只需要找

离左端点或右两端点最远的那个蚂蚁(最靠近中间朝向更近的边)

(果然一个木桶能装多少水取决于最短的那个木板嘛)

求时间最长时只需要找

离左端点或右两端点最远的那个蚂蚁(最靠近端点朝向更远的边)

所以代码就很好写了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000200];
int main() {
	int T,L,n,Tmin,Tmax;
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d",&L,&n);
		for(int i=0; i<n; i++)
			scanf("%d",&a[i]);
		Tmin=Tmax=0;
		for(int i=0; i<n; i++)
			Tmin=max(Tmin,min(a[i],L-a[i]));
		for(int i=0; i<n; i++)
			Tmax=max(Tmax,max(a[i],L-a[i]));
		printf("%d %d\n",Tmin,Tmax);
	}
	return 0;
}

果然考验智商……

又回忆一遍……发现还是有点脑抽……

-.-

用了C++的代码方式

也算先体验一把~

题目地址：【POJ】[1852]Ants

​

加载中...