Ants (POJ 1852)
2024-10-10 03:24:35
题目描述:
Description
An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.
Input
The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.
Output
For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.
Sample Input
2
10 3
2 6 7
214 7
11 12 7 13 176 23 191
Sample Output
4 8
38 207
代码如下:
#include<iostream>
int Max(int,int);
int Min(int,int);
int main()
{
using namespace std;
int i;
cin >> i;
while(i--)
{
int l;
int num;
cin >> l >> num;
int* pt = new int [num];
for(int j = ;j < num;j++)
cin >> pt[j];
int min_ = ,max_ = ;
for(int j = ;j < num;j++)
min_ = Max(min_,Min(pt[j],l - pt[j]));//最小时间是蚂蚁爬向最近一端
for(int j = ;j < num;j++)
max_ = Max(max_,Max(pt[j],l - pt[j]));//无视不同蚂蚁的区别,可以认为是保持原样交错而过
cout << min_ << " " << max_ << endl;
delete [] pt;
}
return ;
} int Max(int a,int b)
{
return a > b ? a : b;
} int Min(int a,int b)
{
return b > a ? a : b;
}
代码分析:
这道题目的难度不在于用到什么算法,而在于想明白两只蚂蚁相遇然后返回,等同于无视蚂蚁的区别,保持原样交错而过。所以有的题目有时候想多了,反而不得解。
参考书籍:[挑战程序设计竞赛第2版]
最新文章
- 用Myeclipse,包名上有小红叉(表示错误),但是包中的类都是没有错误的+struts2继承ActionSupport时package前面出错
- python之对指定目录文件夹的批量重命名
- Web SQL
- 锋利的jquery-选择器
- 一入python深似海--dict(字典)的一种实现
- JavaScript typeof function()的注意事项
- 分享一个自己写的基于TP的关系模型(四)
- ES6-个人学习笔记二--解构赋值
- IOS 动画的两种方式
- MyEclipse Java基础使用笔记
- python生产随机数案例
- Oracle WorkFlow(工作流)(一)
- 本地的jar包添加到maven库中 jdbc举例
- instrument之Time Profiler总结
- python脚本参数传递
- cron定时任务介绍
- Manacher's Algorithm 马拉车算法
- 使用ffmpeg将海康视频rtsp转为hls
- navicat for mysql 10.1.7 注册码
- zookeeper(三):java操作zookeeper