蓝猫领域 level
获赞
4
粉丝
0
关注
1
看过 TA
1
东南大学
2018
C++
IP属地:未知
暂未填写个人简介
私信
关注
2017-09-28 11:19
已编辑
东南大学 C++
数轴上有很多点,已知各点的位置和移速,求最先相遇的两个点
坂本大佬:按点的坐标排序  然后最早相遇的两个点一定是相邻的两个点  顺序遍历计算依次就行 证明: 假设数轴上N个点分别是x1 x2 x3 ... xn 假设最早相遇的两个点不是相邻的  即xa  xb最早相遇 但是不相邻 则一定存在xp  满足xa<xp<xb 要使得xa和xb相遇  则一定要跨过xp  即要么xa跨过xp和xb相遇  要么xb跨过xp与xa相遇 无论那种情况 在xa和xb相遇之前   都是先有xa和xp 或者xb和xp相遇  不满足xa和xb最先相遇的假设 因此  最先相遇的两个点一定是数轴上相邻的两个点
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务