河中跳房子(信息学奥赛一本通-T1247)

2024-06-17 23:32

本文主要是介绍河中跳房子(信息学奥赛一本通-T1247),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目描述】

每年奶牛们都要举办各种特殊版本的跳房子比赛,包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行,在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间,有N (0 ≤ N ≤ 50,000) 个岩石,每个岩石与起点的距离分别为Di (0 < Di < L)。

在比赛过程中,奶牛轮流从起点出发,尝试到达终点,每一步只能从一个岩石跳到另一个岩石。当然,实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移,看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行,他感到非常厌烦。他计划移走一些岩石,使得从起点到终点的过程中,最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后,最长可能的最短跳跃距离是多少?

【输入】

第一行包含三个整数L, N, M,相邻两个整数之间用单个空格隔开。

接下来N行,每行一个整数,表示每个岩石与起点的距离。岩石按与起点距离从近到远给出,且不会有两个岩石出现在同一个位置。

【输出】

一个整数,最长可能的最短跳跃距离。

【输入样例】

25 5 2
2
11
14
17
21

【输出样例】

4

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#define INF 999999999
#define N 1000001
#define MOD 1000000007
#define E 1e-12
using namespace std;
int l,n,m;
int a[N];
int judge(int x)
{int i,dis=0,num=0;for(int i=1;i<=n;i++)if(a[i]-dis<x)num++;elsedis=a[i];if(l-dis<x)num++;return num<=m;
}
int main()
{int left,right,mid;cin>>l>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];left=0;right=l;while(left+1<right){mid=(left+right)/2;if(judge(mid))left=mid;elseright=mid;}cout<<left<<endl;return 0;
}

 

这篇关于河中跳房子(信息学奥赛一本通-T1247)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070709

相关文章

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

生信圆桌x生信分析平台:助力生物信息学研究的综合工具

介绍 少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 生物信息学的迅速发展催生了众多生信分析平台,这些平台通过集成各种生物信息学工具和算法,极大地简化了数据处理和分析流程,使研究人员能够更高效地从海量生物数据中提取有价值的信息。这些平台通常具备友好的用户界面和强大的计算能力,支持不同类型的生物数据分析,如基因组、转录组、蛋白质组等。

【生物信息学算法】图算法1:概念和算法

文章目录 1. 图的定义、分类、表达方式图的定义图的分类表达方式Python实现 2.相邻节点和度概念定义python实现 3.路径、距离和搜索路径和距离搜索环 4.图论中的欧拉定理 1. 图的定义、分类、表达方式 图的定义 图G可以由两个集合来定义,即G=(V,E)。其中,V是对象的集合,称为图的顶点或节点; E是V中(u,v)顶点对的集合,称为边或弧,表示u和v之间的关系

【简历】25届南京某一本JAVA简历:简历通过率还好,但是拿不到OFFER

注:为保证用户信息安全,姓名和学校等信息已经进行同层次变更,内容部分细节也进行了部分隐藏 简历说明 今天看一份25届南京某一本大学的Java简历。 这个简历呢,学校是一本。我们说上来先要定校招层次,这个层次就按照中厂来讲。因为现在很多的双非一本目标都是在中厂。 这个同学有个实习经历,一本有八成的同学主项目都是重复的。HR他只能看到项目重不重复,要点对不对他不知道,就从这个角度来看,这位同学

信息学奥赛初赛天天练-83-NOIP2014普及组-基础题2-输入设备、输出设备、操作系统、二进制、整数除法、while、do while循环

1 NOIP 2014 普及组 基础题2 4 以下哪一种设备属于输出设备( ) A 扫描仪 B 键盘 C 鼠标 D 打印机 5 下列对操作系统功能的描述最为完整的是( ) A 负责外设与主机之间的信息交换 B 负责诊断机器的故障 C 控制和管理计算机系统的各种硬件和软件资源的使用 D 将没有程序编译成目标程序 11 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( ) A 296

基于R语言生物信息学大数据分析与绘图

随着高通量测序以及生物信息学的发展,R语言在生物大数据分析以及数据挖掘中发挥着越来越重要的作用。想要成为一名优秀的生物数据分析者与科研团队不可或缺的人才,除了掌握对生物大数据挖掘与分析技能之外,还要具备一定的统计分析能力与SCI论文质量绘图能力。大量生物数据分析案例,包括利用R语言绘制SCI高质量图片、利用R语言分析生物学数据的案例。 原文链接:基于R语言生物信息学大数据分析与绘图

生物信息学:DNA序列的构成

DNA序列是由一串字母表示的真实的或者假设的携带基因信息的DNA分子的一级结构。‌ DNA序列的构成基于四种特定的碱基,分别是腺嘌呤(A)、胸腺嘧啶(T)、鸟嘌呤(G)和胞嘧啶(C)。这些碱基以特定的配对方式形成碱基对,即A与T配对,C与G配对,这是基于它们之间的氢键相互作用。每个碱基代表一个特定的遗传信息,通过这些碱基的排列顺序,DNA序列能够编码遗传信息,进而指导生物体的生长、发育和功能。

信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶子节点、完全二叉树叶子节点

NOIP 2015 普及组 基础题5 21 重新排列 1234使得每一个数字都不在原来的位置上,一共有( )种排法 22 一棵结点数为 2015的二叉树最多有( )个叶子结点 2 相关知识点 1) 错位排列 考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n) 错排问题最早被尼古拉·伯努利和欧拉研究

【简历】25届重庆某一本JAVA简历:比赛项目描述都是无用的废话

注:为保证用户信息安全,姓名和学校等信息已经进行同层次变更,内容部分细节也进行了部分隐藏 简历说明 这是一个重庆某一本大学25届硕士的Java简历,这个简历,其实还是有一定东西的,然后我们说这个,这是一个重点类的一个一本,所以我们说就按照大厂来讲,但是,其实这后面的这个项目经历不行,就按大厂来讲吧,但是这个按大厂的话,这个学校在大厂里面是最差的一个背景了,他是个减分项,项目这块呢,优势不强啊,

信息学奥赛初赛天天练-79-NOIP2015普及组-基础题4-即时通讯软件、二叉树遍历、前序遍历、中序遍历、后序遍历、算法时间复杂度

NOIP 2015 普及组 基础题4 11 下面哪种软件不属于即时通信软件( ) A QQ B MSN C 微信 D P2P 16 前序遍历序列与中序遍历序列相同的二叉树为( ) A 根结点无左子树 B 根结点无右子树 C 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D 只有根结点的二叉树或非叶子结点只有右子树的二叉树 18 下列选项中不属于视频文件格式的是( ) A TXT B AV