首页 > 跳石头
开通博客写题解
头像 savage
发表于 2019-09-01 18:53:00
题目描述 一年一度的“跳石头”比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点 展开全文
去ta的博客 赞 (24) 回复(2) 收起
头像 馋粉
发表于 2022-06-21 23:28:06
解析 按照答案二分 跳跃距离为0~L 二分判断条件是所有小于跳跃距离的的数量 细节： 右边界找到的结果是大于待查找结果的第一个元素，在这个题目中，就相应地转化为小于目标元素的第一个值，答案为l+1或r+1 若想答案为l或r，check函数改成 bool check(int k){ int 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 CalvinLin011010
发表于 2022-08-06 22:09:46
题目链接： https://ac.nowcoder.com/acm/problem/16462 题面： 一年一度的“跳石头”比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-04 14:21:24
一个寻找最小的尽量大的题目，做这种题目首先要考虑是否可以使用二分验证的方式，因为这种题目的答案在一个单调区间里面寻找。所以可以通过二分答案加一验证的方式快速寻找的答案。 那么要考虑的就是如何验证是否可行，在本题中使用双指针的策略。last保存上一个石头，如果长度符合那么就让last和i都增加， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 东溪看水
发表于 2020-06-12 11:23:56
解题思路 一段长为 L 的路径上有 N + 2 个点，其中两个点位于路径端点，第 i 个点与第 i+1 个点之间的距离为 jump[i]。最多可以消除 M 个点，但不能消除路径两边的端点。求相邻两点之间最短的距离的最大值。 对相邻两点之间最短距离 mid 使用二分法。显然，mid >= 1 且 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 阿威敲快乐
发表于 2023-11-14 21:00:02
通过二分枚举判断最小距离的最大值，判断达到该值要移除的石头个数与要求移除石头个数作比较，进而判断距离的增减 #include<bits/stdc++.h> #include<unordered_map> #define IOS ios::sync_with_stdio(fa 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 savage
发表于 2019-09-06 16:46:57
算法知识点：二分，贪心 复杂度： 解题思路： 如果长度 可以满足，那么当长度小于 时也可以满足，所以我们可以二分出最大的 。 剩下的问题是如何判断给定 的情况下，能否最多拿走 块石头，使得所有相邻两块石头之间的距离不小于。 这一步可以贪心来做。从前往后扫描，并记 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”