【C++题解】NOIP2015提高组 - 跳石头

news/2024/10/30 15:21:14/

✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址:杂题讲解
📝原题地址:跳石头
📣专栏定位:在这里我将整理一些其他比赛或面试的题解~
❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创作的最大动力💪

问题描述

一年一度的“跳石头”比赛又要开始了!

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。

组委会已经选择好了两块岩石作为比赛起点和终点。

在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。

在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。

由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

输入格式

输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。

接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L) 表示第 i 块岩石与起点的距离。

这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出格式

输出文件只包含一个整数,即最短跳跃距离的最大值。

数据范围

0≤M≤N≤500000
1≤L≤109

输入样例:

25 5 2 
2
11
14
17 
21

输出样例:

4

思路

这道题是二分套路题中的经典问题 —— 最小值最大化,除此之外还有最大值最小化问题,解法和这个差不太多。

我们先来考虑暴力法如何做,需要枚举 n 块石头中选取 m 个石头的所有组合,时间复杂度直接爆炸!

所以需要优雅一点的暴力,同样是枚举,不过我们枚举的是最短距离的最大值 d。对这个临界值进行二分,每次二分都去判断当前最短距离的最大值是否能通过移走 m 个以内的石头达到中位值 mid,如果满足条件,则使 left=mid,反之使 right=mid-1,因为我们要使最小值尽可能的大,所以当 mid 已经满足条件时我们任然要继续往更大的值进行尝试,另外 mid 如果此时已经满足条件则有可能就是最终答案,所以需要用 left 保存下来。

另外,我们 check 中可以采用贪心思想:

  • 如果当前石头和上一块石头的距离小于 len,则将当前石头拿走。这是因为如果某个最优解中是拿走了上一块石头,那么我们可以改成留下上一块石头,拿走当前这块石头,这样总共拿走的石头数量不变,所以当前选法也是一组最优解。
  • 如果当前石头和上一块石头的距离大于等于 len,则将上一块石头更新成当前这块。

扫描结束后观察拿走的石头数量是否小于等于 m,如果小于等于则满足条件。

代码

#include<cstdio>
int len, n, m;
int stone[50005];
bool check(int d) {   //检查距离d是否合适int num = 0;       //num记录搬走石头的数量int pos = 0;       //当前站立的石头for (int i = 1; i <= n; ++i)if (stone[i] - pos < d)  num++;          //第i块石头可以搬走else                  pos = stone[i];   //第i块石头不能搬走if (num <= m) return true;  //要移动的石头比m少,满足条件else return false;         //要移动的石头比m多,不满足条件
}
int main() {scanf("%d%d%d", &len, &n, &m);for (int i = 1; i <= n; ++i) scanf("%d", &stone[i]);stone[++n] = len;int L = 0, R = len, mid;while (L < R) {mid = L + (R - L + 1) / 2;if (check(mid)) L = mid;  //满足条件else           R = mid - 1;  //不满足条件,说明mid大了,调小一点}printf("%d\n", L);return 0;
}

http://www.ppmy.cn/news/21420.html

相关文章

RabbitMQ面试题

什么是 MQ MQ(message queue)&#xff0c;从字面意思上看&#xff0c;本质是个队列&#xff0c;FIFO 先入先出&#xff0c;只不过队列中存放的内容是 message 而已。 还是一种跨进程的通信机制&#xff0c;用于上下游传递消息。 在互联网架构中&#xff0c;MQ 是一种非常常见的…

弱网测试利器-Charles工具实战

一&#xff1a;弱网测试要点 二&#xff1a;利用抓包工具charles进行弱网设置&#xff0c;适用PC端和移动端&#xff08;IOS&#xff0f;Android&#xff09; 1、以charles 4.5.6版本为例&#xff0c;打开Proxy->Throttle Settings 2、打开Throttle Settings&#xff0c;界…

【Linux】十分钟快速了解Linux常用指令(建议收藏)

目录&#x1f496;一. 关机指令01. shutdown02. halt03. reboot&#x1f496;二. 常用指令04. ls05. pwd06. cd07. touch08. mkdir09. rm10. man11. cp(复制)12. mv指令13. nano14. cat15. less16. head17. tail18. find19. grep20. zip/unzip21. tar&#x1f496;三、 日期指令…

重写QTableView类解决鼠标右击、单击、双击问题(附使用方法)

目录 一.重写响应事件 1.区分单击和右击 如何使用 2.区分单击和双击 3.其他修改 二.eventFilter截获事件&#xff08;待验证&#xff09; 界面上的QTableView在点击右键想出现右键事件的时候&#xff0c;同时把单击对应的槽函数执行了一遍&#xff0c;所以需要处理做一下…

二分算法学习

&#x1f33c; 扎着马尾的姑娘&#xff0c;笑容温柔很善良自在的少年 - 要不要买菜 - 单曲 - 网易云音乐 前言 本来打算做蓝桥杯2022&#xff23;&#xff0b;&#xff0b;A组省赛F题青蛙过河的,看到标签显示"二分",第一时间竟然想不到二分是什么,所以来学习下 目录…

List、Set、Map的区别

List、Set、Map的区别 ​ &#xff08;图一&#xff09; 1.面试题&#xff1a;你说说collection里面有什么子类。 &#xff08;其实面试的时候听到这个问题的时候&#xff0c;你要知道&#xff0c;面试官是想考察List&#xff0c;Set&#xff09; 正如图一&#xff0c;lis…

leetcode刷题记录总结-7.递归回溯算法(进行中)

文章目录零、回溯算法理论总览什么是回溯法回溯法的效率回溯法解决的问题如何理解回溯法回溯法模板一、组合问题[77. 组合](https://leetcode.cn/problems/combinations/)题解递归实现组合型枚举&#xff1a;每个点选与不选子集问题模板组合问题解决思路回溯思路&#xff1a;遍…

这都能第六?

文章目录&#x1f31f; 专栏介绍&#x1f31f; Vue默认版本&#x1f31f; 拥抱Vue3的UI&#x1f31f; Vue3显著优势&#x1f31f; 专栏介绍 凉哥作为 Vue 的忠诚粉丝输出过大量的 Vue 文章&#xff0c;应粉丝要求开始更新 Vue3 的相关技术文章&#xff0c;Vue 框架目前的地位大…