首页 > 聚会
开通博客写题解
头像 精神病科黄主任
发表于 2020-04-17 23:30:06
考虑二分答案。二分出来mid，那么对于绝对值≤mid的，我们不需要管他，因为他可以直接走到原点，在mid时间内一定可以到。那么对于剩下的呢？我们对于剩下的去找最大值max和最小值min，如果max - min <= 2 * mid,说明mid这个是满足答案的，那么就需要下降二分上界，至于一个门 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 ZevenWu
发表于 2020-04-18 09:18:56
solution：设mx为最大点的坐标，mi为最小点的坐标的绝对值。不妨设mi<mx。则上限为mx。首先有一个结论：一定有一个点在原点。证明如下：分类讨论，不妨设左边叫A，右边叫B。若A<B<0：这种答案就为上限。若A<0<B：在这种情况下，A、B绝对值较小的那一边的所 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 wxyww
发表于 2020-04-19 11:16:52
solution 显然答案具有单调性，所以二分一个答案，也就是最后一个人到达的时间。 这样距离原点小于等于的点就都不用考虑了。然后目标就是放置一个传送门，使得其他的点与传送门之间的距离小于等于。显然将传送门放在这些点的中间最优秀。所以只要找到最靠右和最靠左的两个点，看他们之间的距离是不是小于等于即可 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Kur1su
发表于 2020-04-17 22:32:42
A. 聚会 Solution 跟出题人的做法不太一样?我是考虑二分答案, 我们先从小到大排个序当我们二分一个x时, x是我们的备选答案(即最晚到达时间), 他可能过大, 也可能过小, 我们需要check一下我们从左往右遍历全部点, 如果当前的点跟 0 点的距离大于 x 且当前还没有建造过传送门, 就 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 Meul
发表于 2020-04-19 13:46:38
Question 一个数轴，牛牛的家在0点处，在道路上的整数点上建立两个传送门，朋友们可以通过传送门从一个位置瞬间传送到另一个位置，在最优策略下，朋友们最晚需要多长时间可以到达聚会地点？ Solution 答案具有单调性，二分答案。接下来就是check函数怎么写的问题了。 牛牛的朋友到0点距离小于 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-04-24 11:05:42
二分一个传送门肯定放终点，另一个我们用二分来求sum。在sum之内的点不需要考虑，我们要使sum之外的点到sum的距离都小于mid，让另一个传送门可以覆盖2mid的区域当最左端和最右端的距离小于2*mid时，就可以缩小R #include <bits/stdc++.h> #include 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 漂洋过海sail
发表于 2020-04-18 17:22:20
题意 一条数轴上有 个点，设两个传送门，可互相瞬间传送，求这 个点移动到原点最短时间。 算法（） 二分答案，一个传送门必定设在原点，另一个传送门可覆盖 的区域，线性判定答案可行性。 代码 #include <cstdio> #include <algorithm> u 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”