题目分享R
题意:有n只蚂蚁在木棍上爬行,每只蚂蚁的速度都是每秒1单位长度,现在给你所有蚂蚁初始的位置(蚂蚁运动方向未定),蚂蚁相遇会掉头反向运动,让你求出所有蚂蚁都·掉下木棍的最短时间和最长时间。
分析:(其实很久之前在洛谷上就做过一个类似的题,好像叫独木桥)
考虑对于两个人相遇的过程,以及最后结果的最值
第一个人位置为x1,第二个人位置为x2,其中x2>x1
这里就有两人分别朝左朝右共有4种情况
1.第一个人朝左,第二个人朝左
显然第一个人掉下去的时间是x1,第二个人掉下去的时间是x2,总用时就是x2
2.第一个人朝左,第二个人朝右
显然第一个人掉下去的时间是x1,第二个人掉下去的时间是l-x2,总用时就是max(l-x2,x1)
3.第一个人朝右,第二个人朝右
显然第一个人掉下去的时间是l-x1,第二个人掉下去的时间是l-x2,总用时就是max(l-x1,l-x2)
4.第一个人朝右,第二个人朝左
这就不显然了,这样他们会发生相遇,并且掉头走,首先他们相遇的时间是(x2-x1)/2 ,他们相遇的位置就是(x1+x2)/2 ,他们分别往回返并掉下去的时间就是(x1+x2)/2 和l-(x1+x2)/2
那么总用时就是(x2-x1)/2+(x1+x2)/2和(x2-x1)/2 +l-(x1+x2)/2 中的最大值,化简就是max(x2 ,l-x1)
那么最短用时就是min(x2,max(l-x2),max(l-x1,l-x2),max(x2,l-x1)) ,最大值也同理,再与x1<x2关联一下,很容易发现,结果其实就是min(max(x1,l-x1),max(x2,l-x2)) 与max(max(x1,l-x1),max(x2,l-x2))
也就是说其实最小值就是把所有人的max(xi,l-xi)取最小,而最大值就是取最大
当然这还有另一种理解,就是两个人他们是完全等效的,相遇折返其实就是相当于两个人互相穿过对方,所以也可以写出这个式子来
代码:
#include<cstdio>
#include<algorithm>
using namespace std; int main()
{
int t,l,n,i,a;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&l,&n);
int minans=,maxans=;
for(i=;i<n;i++)
{
scanf("%d",&a);
minans=max(minans,min(a,l-a));
maxans=max(maxans,max(a,l-a));
}
printf("%d %d\n",minans,maxans);
}
return ;
}
最新文章
- 在易语言中调用MS SQL SERVER数据库存储过程方法总结
- 根据osdid 查询磁盘是ssd盘还是sas盘
- 据说每个大牛、小牛都应该有自己的库——DOM处理续
- 常用正则表达式(?i)忽略字母的大小写!
- php快速定位多维数组的深度
- SharePoint:备份和还原
- Ubuntu下vim中文乱码
- go的gin框架从请求中获取参数的方法
- xbee无线通讯终端
- 使用First查找集合报错:序列不包含任何匹配元素
- ajax跨域原理和cors跨域资源共享
- 单点登录SSO+鉴权
- Bootstrap表格中,thead固定,tbody有垂直滚动条
- CSS border-radius边框圆角
- 用户登录页面——jdbc
- IDFA
- Python 进程间的通信
- 解决Chrome关联Html文件图标显示为空白
- Web—07-JQuery
- Java 异常总结
热门文章
- java day04记录
- spark sql error mismatched input &#39;union&#39; expecting { <;EOF>;,&#39;&#39;................................
- 初探CI,Github调戏Action手记——自动构建并发布
- 【docker】为docker下的php容器安装php-redis扩展【编译安装】
- 浅谈ArrayList
- 官方解读:Salesforce线上考试新政与福利
- Windows下如何将一个程序设为开机自启
- radio取值
- AI-web-1靶机过关记录
- Golang交付至Kubernetes