POJ 1852 Ants(弹性碰撞问题)_纯真zwj的博客-程序员秘密

技术标签: ACM常用技巧  

Ants

Time Limit: 1000MS


Memory Limit: 30000K

Total Submissions: 12607


Accepted: 5525

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


题意:在一根长为L的水平木棍上有一群数量为n的蚂蚁,它们以每秒1cm/s的速度走到木棍一端就会掉下去。现在知道它们的起始位置是距离木根左端点的x处。但是不知道它们爬行的方向。在相向而行的两只蚂蚁相遇后,它们会掉头往反方向走。问所有蚂蚁都落下木棍的最快时间和最慢时间。


题解:一开始觉得可以暴搜,每只蚂蚁只有两种情况,不过掉头的事情感觉很复杂。时间复杂度为2的n次幂。肯定超时。  因为是同时出发的,相遇时的两只蚂蚁用的时间是相同的,我们可以无视蚂蚁的区别,当两只蚂蚁相遇时它们保持原样交错而行。这样每只蚂蚁都是独立运动的,那么只要找每只蚂蚁掉下去的时间就行了。


代码如下:


#include<cstdio>
#define maxn 1000100
int a[maxn],ansmin,ansmax,L,n;

int MIN(int a,int b)
{
	return a<b?a:b;
}

int MAX(int a,int b)
{
	return a>b?a:b;
}

void ansMIN()
{
	int i,min;
	ansmin=-1;
	for(i=0;i<n;++i)
	{
		min=MIN(a[i],L-a[i]);
		if(min>ansmin)
			ansmin=min;
	}
	printf("%d ",ansmin);
}

void ansMAX()
{
	int i,max;
	ansmax=-1;
	for(i=0;i<n;++i)
	{
		max=MAX(a[i],L-a[i]);
		if(max>ansmax)
			ansmax=max;
	}
	printf("%d\n",ansmax);
}

int main()
{
	int i,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&L,&n);
		for(i=0;i<n;++i)
			scanf("%d",&a[i]);
		ansMIN();//求所有蚂蚁掉下去的最短时间 
		ansMAX();//求所有蚂蚁掉下去的最长时间 
	}
	return 0;
} 




版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zwj1452267376/article/details/49820483

智能推荐

Django框架_XWenXiang的博客-程序员秘密_django框架

文章目录Django文件解析Django文件解析mysite/ manage.py mysite/ __init__.py settings.py urls.py asgi.py wsgi.py 1. 外层的mysite/目录与Django无关,只是你项目的容器,可以任意重命名。2. manage.py:一个命令行工具,管理Django的交互脚本。3. 内层的mysite/目录是真正的

Power over Ethernet - Understanding PoE Technol..._weixin_33724046的博客-程序员秘密

为什么80%的码农都做不了架构师?&gt;&gt;&gt; ...

嵌套makefile范例_qq_36831356的博客-程序员秘密_makefile嵌套

这里参考一些其他文章的实例编写而成的,稍作修改,也更详细一点

GLFW的使用_铿锵的玫瑰的博客-程序员秘密

GLFW是一个专门针对OpenGL的C语言库,它提供了一些渲染物体所需的最低限度的接口。它允许用户创建OpenGL上下文,定义窗口参数以及处理用户输入。 GLFW的下载地址:http://www.glfw.org/download.html 如果要使用预编译的二进制版本的话,请下载32位的版本而不是64位的。 从源代码编译库可以保证生成的库是兼容你的操作系统和CPU的,而预编译的二进制文...

【Nginx】如何配置Nginx日志?这是最全面的一篇了!!_冰 河的博客-程序员秘密

写在前面日志对于统计排错来说非常有利的。本文总结了 Nginx 日志相关的配置如 access_log、 log_format、open_log_file_cache、 log_not_found、 log_subrequest、 rewrite_log、 error_log。配置Nginx日志Nginx 有一个非常灵活的日志记录模式。每个级别的配置可以有各自独立的访问日志。日志格式通过 log_format命令来定义。 ngx_http_log_module 是用来定义请求日志格式的。ac

IEEE802.15.4 部分无线收发芯片比较_weixin_34409822的博客-程序员秘密

见下表:TI(CC2530&amp;CC2520)ST(STM32W108)Atmel(AT86RF231)功耗(发送功率0DB)30mA31mA14mA是否提供手册提供不提供提供是否具有例程有有无,但有指导文档冲突检查否否是硬件标准IEEE802.15.4...

随便推点

简单声音编辑 - 删减 加速_catsender的博客-程序员秘密

有的时候需要对一些拿到的声音效果进行编辑,以达到要求。 删减:https://www.apowersoft.cn/free-online-audio-editor 这个网站可以进行免费的声音编辑,在线的,不过要装一个插件才可以。不过不能对声音进行加减速加减速可以用这个软件:无瑕音频变调变速器 官网:点击下载会调到百度云,下载之后直接就可以使用,免安装版本,亲测好用 http://www...

Idea加载MySQL本地驱动_BY&Crystal的博客-程序员秘密

请参考:https://blog.csdn.net/Bzbtyhydcxy/article/details/106691698

CSS的换行方式_qq_44635639的博客-程序员秘密_换行css

1.自动换行word-wrap:break-word;word-break:normal;2.强制英文单词断行word-break:break-all;3.强制不换行white_space:white-space:nowrap;

XWiki_安装和基础配置企业级知识库_weixin_34211761的博客-程序员秘密

背景在平时的工作中,把常规工作进行文档整理非常重要,无论是平时工作处理或是工作交接,实时的维护文档资料可以提高工作效率。如果采用传统的TXT文档或者Word文档来记录的话修改查询都不太方便,采用在线Wiki可以更好的让大家实时地查看或者修改文档资料。在开源Wiki系统中,XWiki是做的最好的产品之一。因为它提供的功能与Confluence的功能非常相似,不需要学习任何语法格式,可以直接在线像...

java 输入输出ppt_Java的文件(读写)输入输出.ppt_weixin_39630771的博客-程序员秘密

Java的文件(读写)输入输出.pptJava程序设计语言;昨天重点内容回顾;内容安排;输入/输出处理;输入/输出处理;输入/输出处理;输入/输出处理;输入/输出处理--- java.io包;控制台I/O;向标准输出上写;文件和文件I/O;java.io.File类中的一些函数;文件流I/O;基本流类;字节流;字符流;I/O流链;Processing Streams;其它;InputStream;...

<<Python基础教程>>学习笔记 | 第07章 | 更加抽象_杰瑞26的博客-程序员秘密

Python:面向对象的编程语言,多态,封装,继承三个主要特性多态:来自希腊语,意味着有多种形式。>>> from random import choice>>> x = choice(['Hello,World!',[1,2,'e','e',4]])>>> x.count('e')1任何不知道对象到底是什么类型,但又要对对象做的什么的时候,就要用到多态>>> 1+23>>> 'hot'+'dog''hotdog'#和下面的形式是一样的>>> def add(x,y): return

推荐文章

热门文章

相关标签