首页 > 其他分享 >[NOIP2015 提高组] 跳石头

[NOIP2015 提高组] 跳石头

时间:2024-06-03 21:12:52浏览次数:25  
标签:NOIP2015 le int 岩石 距离 石头 终点 提高 起点

[NOIP2015 提高组] 跳石头

跳石头

题目描述

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

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 $N$ 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 $M$ 块岩石(不能移走起点和终点的岩石)。

输入格式

第一行包含三个整数 $L,N,M$,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。

接下来 $N$ 行,每行一个整数,第 $i$ 行的整数 $D_i,( 0 < D_i < L)$, 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出格式

一个整数,即最短跳跃距离的最大值。

样例输入 #1
25 5 2 
2
11
14
17 
21
样例输出 #1
4

提示

输入输出样例 1 说明

将与起点距离为 $2$ 和 $14$ 的两个岩石移走后,最短的跳跃距离为 $4$(从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石,或者从距离 $21$ 的岩石跳到终点)。

数据规模与约定

对于 $20%$的数据,$0 \le M \le N \le 10$。
对于 $50%$ 的数据,$0 \le M \le N \le 100$。
对于 $100%$ 的数据,$0 \le M \le N \le 50000,1 \le L
\le 10^9$。


算法1

(二分答案) $O(logn)$

1.二分什么:最短跳跃距离
2.二分边界:int l = 0,r = len; 起点到终点
3.判断依据: 移动的石头个数
(1) 当移动的石头个数少,说明条约距离太小了
当前跳跃距离是合法的解,但找最优解-可以再大点
往后找—— l = mid + 1;
(2) 当移动的石头个数多了说明条约距离太大了
从往前找 - 需要把范围变小
r = mid - 1;
4.找出最短距离的最大值
ans = max( ans, mid);
5.需要注意的点:
(1)把终点的石头补上

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+7;
#define int long long 

int len,n,m;
int a[N];
bool check(int k){
	int sum=0,tmp=0;
	for(int i=1;i<=n+1;i++){
		if(a[i] - tmp >= k) {
			
			tmp=a[i];//跳到该石头上 
		}
		else{
			sum++;  //移走该石头 
		} 
	}
	return sum <= m;  
}
signed main(){
	
	cin>>len>>n>>m;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1]=len; //补上终点的石头
	
	int l=0,r=len;
	int ans=0;
	while(l <= r){ 
		int mid = l + r >> 1;
		if(check(mid)) {
			ans=max(ans,mid);
			l = mid + 1 ;//合法答案说明可以找更大的值 
		}
		else{
			r = mid -1 ; //如果移动的个数多了 -说明跳跃距离太大了 
		} 
	} 
	cout<<ans;
	
	return 0;
}

标签:NOIP2015,le,int,岩石,距离,石头,终点,提高,起点
From: https://www.cnblogs.com/ltphy-/p/18229663

相关文章

  • 抖音团购外卖代理怎么提高申请成功率?
    作为多家互联网大厂重点布局和大力发展的业务板块,近年来,本地生活服务的热度不断上升。其中,日活跃用户超过10亿人次的抖音团购外卖则是当之无愧的后起之秀,抖音外卖团购代理的申请人数更是与日俱增。​而在所有抖音外卖代理申请渠道中,可行性最高的便是走抖音官方渠道或申请第三......
  • GCB | 基于36年5个生态系统观测数据发现表层土壤深度提高生态系统的生产力和稳定性
    陆地生态系统生产力对全球粮食安全和促进碳固存至关重要,但生产力受到气候变化以及火灾、干旱、洪水、霜冻频率增加和生物多样性减少的压力。了解控制生态系统初级生产力变异的不同因素和机制,为维持生态系统初级生产力和增强生态系统恢复力提供了科学依据。土壤是陆地碳、养分......
  • 论文降重新策略:笔灵AI降重如何提高论文质量?
    论文降重一直是困扰各界毕业生的“拦路虎”,还不容易熬过修改的苦,又要迎来降重的痛。其实想要给论文降重达标,我有一些独家秘诀。话不多说直接上干货!1、同义词改写(针对整段整句重复)这是最靠谱也是比较费精力的办法,就是在保证同义的情况下改写内容,幅度要大。往往需要整段改写,一......
  • Java中的依赖注入:提高代码的可维护性和可测试性
            依赖注入(DI)是一种软件设计模式,旨在实现控制反转(IoC),通过这种方式,对象的依赖项(通常是服务)不由对象本身创建,而是由外部容器动态提供。在Java中,依赖注入是实现松耦合和增强代码可维护性的有效手段。本文将探讨Java中的依赖注入概念、其优势以及如何利用现有的框架......
  • WinDbg基本原理和使用方法,掌握基本的调试技术,并能够应用于实际的调试工作中;高级调试技
    WinDbg初级应用的大纲:1.WinDbg基础知识WinDbg简介:介绍WinDbg是什么以及其在Windows调试和分析中的作用。安装与配置:指导学员如何安装和配置WinDbg调试环境,包括下载安装、符号配置等基本步骤。2.调试基础调试流程:解释调试的基本流程,包括启动目标程序、设置断点、执行程序......
  • ProcDump工具的基本用法和功能,并掌握如何利用它进行进程监视、性能分析和故障排查,从而
    ProcDump初级应用的大纲:1.ProcDump简介与基本用法介绍ProcDump工具的基本作用和功能。演示如何使用ProcDump来监视进程并在满足指定条件时生成转储文件。2.进程监视与性能分析探讨如何使用ProcDump监视进程的CPU利用率、内存占用等性能指标。演示如何利用ProcDump生成......
  • Process Explorer工具,帮助他们更好地管理和监控Windows系统中的进程和系统资源;掌握更
    初级应用ProcessExplorer的大纲:1.ProcessExplorer简介简要介绍ProcessExplorer工具的作用和用途。解释为什么ProcessExplorer是管理Windows系统进程的有用工具。2.工具界面导览展示ProcessExplorer的主要界面和功能区域。解释各个部分的作用和功能。3.进程查看......
  • YOLOv8: 标注石头、识别边缘及计算面积的方案
    YOLOv8:标注石头、识别边缘及计算面积的方案引言YOLO(YouOnlyLookOnce)是一种非常有效的实时目标检测算法,自其首次发布以来就受到了广泛的关注和应用。YOLOv8是这一系列算法的最新版本,继承了之前版本的高效性和准确性,同时在模型结构和性能上进行了优化。在本文中,我们......
  • day45 1049.最后一块石头的重量II 494.目标和 474.一和零
    1049.最后一块石头的重量II本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。本题物品的重量为stones[i],物品的价值也为stones[i]。对应着01背包里的物品重量weight[i]和物品价值value[i]。思路:动规五部曲1.确定dp数组以及下......
  • Java多线程编程:提高程序性能与响应性
            多线程编程是利用计算机的多核心优势来提高程序的性能和响应性的重要手段之一。在Java中,通过多线程可以实现同时执行多个任务,充分利用CPU资源,加速程序的运行。本文将深入探讨Java多线程编程的基本概念、常用类库、并发问题以及最佳实践。####1.多线程基础概......