杨佳奇yjq

用户名：dotcpp0611928

访问量：992

签　名：

求知若饥，虚心若愚

等　　级
排　　名	2358
经　　验	2343
参赛次数	22
文章发表	4
年　　龄	18
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

题目 3241: 蓝桥杯2024年第十五届省赛真题-挖矿
浏览：206

题目 3241: 蓝桥杯2024年第十五届省赛真题-挖矿
浏览：200

蓝桥杯2024年第十五届省赛真题-封闭图形个数
浏览：307

你可能喜欢

题目 3241: 蓝桥杯2024年第十五届省赛真题-挖矿

　　作者: 杨佳奇yjq　　　　发表时间：2024-05-08 09:43:48 浏览：200　|　评论：0　

原题链接：蓝桥杯2024年第十五届省赛真题-挖矿

# 二分题解
> 食用之前请先来一发暴力更有利于理解题意	:D

## 1、为什么用二分？
>由于不知道要访问多少个坐标，于是我们就来枚举有多少个，
>发现时间复杂度为 O(n^2)，而这里 1≤n≤10^5 会超时，于是就想到了用二分优化。

## 2、二分思路：
>开挖挖机挖矿石
>题目问的是最多可以挖多少矿石。
>稍稍分析可知，多访问一个矿洞，时间必定不会减少，显然这具有单调性质。于是很自然的可以想到去二分矿洞的个数鸭。
>QwQ
>先将所有矿洞的位置排序。要尽量使用时最少，那么我访问的任意两个矿洞之间都不能有其他的东西。
>（因为如果我访问的两个矿洞之间还有矿洞，那我还不如把这个矿洞顺便一起挖了呢）
>
>那么，在存储矿洞位置的容器中，只要排好序，我访问的矿洞就一定是下标相邻的。
>二分能访问到的矿洞个数，枚举右端点（当然左端点也行），判断这个区间是否能在 m 距离内访问完成。
>
>最后右端点枚举完了，如果还没有找到解，那就证明当前二分的这个矿洞个数不行。
><br />一直二分就行了。

## 3、代码如下：
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
#define rep(i, a, b) for( int i=(a); i<=(b); i++)
#define MAXN 1e6+10
using namespace std;

int n,m;
vector<int > a(MAXN);

bool check(int x){
	//枚举右端点
	rep(r, x, n){
		int l = r - x + 1;

//如果右端点在原点左边，就要一直向左走
		if(a[r] < 0)
			if(-a[l] <= m)
				return 1;

//如果左端点在原点右边，就要一直向右走
		if(a[l] >= 0)
			if(a[r] <= m)
				return 1;

//如果这段区间横跨了原点
		if(a[l]<=0 && a[r]>=0)
			//先去距离原点短的那一边，再走到另一边
			if(min(a[r],-a[l])+a[r]-a[l] <= m)
				return 1;
	}
	//无解返回 false
	return false;
}

signed main(void) {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >>n >>m;
	//注意：我的数据是从下标为1开始进行存入的
	rep(i, 1, n){
		cin >>a[i];
	}
	//此题的距离满足单调性，用algorithm库里的sort函数对此进行排序
	sort(a.begin()+1,a.begin()+1+n);

//二分模板
	//因为数据是从下标为1开始存入的，l的数据范围要小于1，也就是0
	//如果数据是从下标为0开始存，则l的就不能为0，应该为-1
	int l = 0, r = n+1;
	while (l+1 < r)
	{
		int mid = (l+r) >>1;
		if(check(mid)){
			l = mid;
		}else{
			r = mid;
		}
	}
	cout <<l <<endl;
	return 0;
}
```
# QwQ

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

杨佳奇yjq

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

题目 3241: 蓝桥杯2024年第十五届省赛真题-挖矿

评论区

精彩推荐

程序员的表白（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

大家好，我是验题君

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

简单的a+b （C语言代码）

C语言训练-8除不尽的数（C语言代码）

多输入输出练习2 （C语言代码）

杨佳奇yjq

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

题目 3241: 蓝桥杯2024年第十五届省赛真题-挖矿

评论区

精彩推荐

程序员的表白 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

大家好，我是验题君

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

简单的a+b （C语言代码）

C语言训练-8除不尽的数 （C语言代码）

多输入输出练习2 （C语言代码）

C二级辅导-分段函数（C语言代码）

　　评论区

程序员的表白（C语言代码）

C语言训练-8除不尽的数（C语言代码）