NOIP2015 跳石头_noip跳石头-程序员宅基地

技术标签： 题目笔记  算法笔记  

最近一直在刷二分答案的题，先来总结一下lyd大佬对于二分答案的解释

在这里插入图片描述

借助二分，我们把求最优解的问题，转化为给定一个值mid，判定是否存在一个可行的方案评分达到mid的问题。

对于跳石头这个题来说，我们可能枚举去掉哪几个石头来构成方案的问题很难，但是我们可以通过二分出来它最后跳跃的最短距离可能是多少来进行选择

从而本质上二分答案讲问题转化为判定问题

最终本题解题思路就是，看看在某一个最短距离的情况下，能不能去掉小于等于m块石头的方案

如果某个距离答案满足了去掉的小于等于m的方案个数，那么我就看看比它小的可以吗，就是求这个可行区间的最小值，就是求答案在右边区间的左端点，这也就说明了应该用哪个二分模版

// Problem: P2678 [NOIP2015 提高组] 跳石头
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2678
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;

int dx[4] = {
    -1,0,1,0};
int dy[4] = {
    0,1,0,-1};

int x, m, n;

int d[50000 + 10];

int len[50000 + 10];

bool check(int le){
    
	int cnt = 0;
	
	int i = 0; 
	int now = 0; // 一开始是在起点的 
	
	while(i < n + 1){
    
		i++;
		if(d[i] - d[now] < le){
    
			cnt++;
		}
		else{
    
			now = i;
		}
	}
	
	return m >= cnt;
	
}

int main(){
    
	cin >> x >> n >> m;
	
	int l = 1;
	int r = x;
	
	for(int i = 1; i <= n; i++){
    
		cin >> d[i];
	}
	
	d[n + 1] = x; // 注意题目给的距离含义，这是中点的位置
	
	while(l < r){
    
		int mid = (l + r + 1) / 2;
		if(check(mid)){
    
			l = mid;
		}
		else{
    
			r = mid - 1;
		}
	}
	
	cout << r << Endl;
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/INGg__/article/details/116240435

智能推荐

docker查看错误日志_docker读取error.log文件-程序员宅基地

文章浏览阅读1.5w次，点赞3次，收藏4次。想创建mysql容器运行，但是发现出错了先通过docker ps -a查到已经被停止的容器的id然后通过docker logs id 来查看相应的日志信息结果如下图：_docker读取error.log文件

程序员好用的软件/网页推荐-程序员宅基地

文章浏览阅读446次，点赞11次，收藏9次。欢迎推荐，持续更新。

C# 利用DIrectoryInfo获取文件名称和大小 写入word文件_winform directoryinfo获取指定文件名称-程序员宅基地

文章浏览阅读202次。C#语言利用DirectoryInfo和排序列表SortedList读取Windows目录中文件和大小，并写入word文件。_winform directoryinfo获取指定文件名称

3-gcc-Makefile-安卓的编译_needed by 'out_hal/target/product/mgvi_t_64_armv82-程序员宅基地

文章浏览阅读101次。编译：把自己写的代码转成计算机能识别的代码，因为计算机只识别二进制的东西。例如把.c文件转为二进制bin文件。百度百科：编译：就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。GNU compiler collection, 是linux下最主要的编译工具，可以通过不同前端模块来支持各种语言，如c,c++,java。g++是gcc中的一个工具，专门用来编译c++语言。_needed by 'out_hal/target/product/mgvi_t_64_armv82/obj_arm/shared_libraries

winfrom弹框提示，确认之后执行其他操作_windows弹出确认消息,再去执行任务-程序员宅基地

文章浏览阅读409次。if (MessageBox.Show("你确定要退出程序吗？", "确认", MessageBoxButtons.OKCancel, MessageBoxIcon.Question, MessageBoxDefaultButton.Button2) == DialogResult.OK){ //确认后，需要执行的操作}_windows弹出确认消息,再去执行任务

SCI期刊：MTAP（Multimedia Tools and Applications）投稿_mtap期刊-程序员宅基地

文章浏览阅读2k次，点赞8次，收藏14次。在MTAP期刊投稿的时候，建议是使用通讯作者的账号进行投稿(期刊默认投稿的作者账号为通讯作者)，我们试过使用非通讯作者的账号进行投稿，搞到后面，需要做重复的手续，因此还是建议使用通讯作者的账号进行投稿。首先，进入MTAP期刊的登录页面。首先需要进行账号注册，其实我挺推荐使用ORECID码的，真的很方便，尤其在最后录用论文的时候，可以自动关联ORCID码，便于自己进行学术成果展示。目前，按照我的投稿情况看，期刊需要有4位审稿人的意见再进行综合裁决，由于审稿人数较多，所以可能需要等的时间比较久。_mtap期刊

随便推点

elasticsearch[一]-索引库操作(轻松创建)、文档增删改查、批量写入(效率倍增)_elasticsearch 添加索引-程序员宅基地

文章浏览阅读1.4k次，点赞17次，收藏24次。elasticsearch[一]-索引库操作(轻松创建)、文档增删改查、批量写入(效率倍增)_elasticsearch 添加索引

【openGauss】谈一谈openGauss对Oracle中lob类型的兼容情况_opengauss blob转bytea-程序员宅基地

文章浏览阅读129次。如果有从oracle迁移到openGauss的，而且有使用二进制数据类型及处理的，一定要谨慎处理这些兼容问题，否则可能会出现代码不报错但数据处理出错的情况。当然，也可以使用compat-tools组件。目前compat-tools已经加入了utl_raw及dbms_lob这两个包，欢迎大家测试使用【openGauss】谈一谈openGauss对Oracle中lob类型的兼容情况。_opengauss blob转bytea

黑马程序员——父类构造函数子类构造过程_利用父类的构造函数实现子类的构造函数-程序员宅基地

文章浏览阅读598次。------- android培训、java培训、期待与您交流！ ----------子父类中的构造函数。在对子类对象进行初始化时，父类的构造函数也会运行，那是因为子类的构造函数默认第一行有一条隐式的语句 super();super():会访问父类中空参数的构造函数。而且子类中所有的构造函数默认第一行都是super();为什么子类一定要访问父类中的构造函数。因为父类中的数据_利用父类的构造函数实现子类的构造函数

有符号二进制数的乘法_二进制负数乘法-程序员宅基地

文章浏览阅读3.8w次，点赞25次，收藏55次。最近在阅读《深入理解计算机系统》讲到补码乘法，书上给了一个例子是三位无符号和补码的乘法表。其中两个负数的例子：3位二进制乘法结果一般需要6为二进制表达带符号数x=101=-3 和y=011=3相乘 结果为110111=-9 如果直接算出来十进制是-9然后转换为6为二进制我也能理解，但是我很好奇他利用了什么规则得出这样的结果。根据结果推过程我认为计算机做计算都要按照正数或者说无符号数_二进制负数乘法

UML类图关系（泛化 、继承、实现、依赖、关联、聚合、组合）_一辆车一个方向盘四个轮胎类图-程序员宅基地

文章浏览阅读8.5k次。聚合是关联关系的一种特例，他体现的是整体与部分、拥有的关系，即has-a的关系，此时整体与部分之间是可分离的，他们可以具有各自的生命周期，部分可以属于多个整体对象，也可以为多个整体对象共享；组合也是关联关系的一种特例，他体现的是一种contains-a的关系，这种关系比聚合更强，也称为强聚合；其他的四者关系则体现的是类与类、或者类与接口间的引用、横向关系，是比较难区分的，有很多事物间的关系要想准备定位是很难的，前面也提到，这几种关系都是语义级别的，所以从代码层面并不能完全区分各种关系；_一辆车一个方向盘四个轮胎类图

Eclipse及其插件介绍和下载_eclipse jsp页面格式化插件-程序员宅基地

文章浏览阅读2.7k次。 Voice Tools project 它为JSP/J2EE领域中的Voice Application提供一组基于Eclipse的开发工具. MiddlegenIDE MiddlegenIDE是一个Middlegen在 Eclipse下的插件,它可生成映射文件,JavaBean源码,配置文件和导入相关的jar.而你所要做的只是配置好数据库连接信息和选择要生成映射文_eclipse jsp页面格式化插件

推荐文章

热门文章

相关标签