【二分查找】分巧克力、机器人跳跃、数的范围

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

 

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

 

开始准备蓝桥杯啦！这是计划的一部分，每天都会更新一个专题的内容，内容参考自acwing蓝桥杯辅导课，有兴趣的uu们也可以自行观看

二分查找模板在前几篇文章中有讲过 二分查找详解

题目:数的范围

给定一个按照升序排列的长度为 n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤100000
1≤q≤100001
1≤k≤100001

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

白话讲解:

非常经典的二分模板 ，通过前面的学习，我们知道二分查找有一个范围的问题，即是mid>= 还是mid>，也就是开闭区间的问题，这题完美诠释了这个特性

代码实现:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int q[N];
int main()
{scanf("%d%d",&n/*正数组长度*/,&m/*查询个数*/);for(int i=0;i<n;i++){scanf("%d",&q[i]);}while(m--){int x=0;scanf("%d",&x);int left=0,right=n-1;while(left<right){int mid=(left+right)>>1;if(q[mid]>=x)right=mid;else left=mid+1;}if(q[left]!=x)cout<<"-1 "<<"-1 "<<endl;else{cout<<left<<" ";int left=0,right=n-1;while(left<right){int mid=(left+right+1)>>1;if(q[mid]<=x)left=mid;else right=mid-1;}cout<<left<<endl;}}return 0;
}

题目:机器人跳跃问题

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 00 到 N 编号，从左到右排列。

编号为 00 的建筑高度为 00 个单位，编号为 i 的建筑高度为 H(i) 个单位。

起初，机器人在编号为 00 的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 k个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E的能量值，否则它将得到 E−H(k+1)的能量值。

游戏目标是到达第 N个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 N。

第二行是 N个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤1e5

输入样例1：

5
3 4 3 2 4

输出样例1：

4

输入样例2：

3
4 4 4

输出样例2：

4

输入样例3：

3
1 6 4

输出样例3：

3

白话讲解:

也就是有一个机器人要进行平台跳跃

若平台比他现在的位置高，则需要扣除h(i)-E的能量,若他比平台高,则能获得E-h(i)的能量,要求跳跃中能量不能为负

题解:

分析两个扣除能量的规则就可以发现,不论高低与否,能量E=2E-h(i) ,也就是能量一直都是这样改变的,判断是否能用二分来搜寻答案最重要的就是判定其是否满足递增的条件(必要不充分),

当找到一个满足条件的E之后,大于E的情况下是都能跳跃过去.所以我们用二分来做.

int的数据范围最大为1e9,而观察这题题设范围,当h(i)足够小的时候,E=2E,有可能爆int,所以我们推断,当E=h(i)max时,此时表达式为E=E+h(i)max-h(i) h(i)无限小,即可忽略不计,所以当E=h(i)max时,即可表示其可跳跃过之后所有的格子.

也可以理解为,当我跳到最高点时,之后都是在增加能量,而不是减少,所以即可判定一定能跳过

另外,刚刚说过了>=E的条件都满足题解,所以这里的二分为left=mid+1 right=mid

不懂我在说什么的uu可以回顾下二分

check函数为:模拟跳跃每一次

代码实现:

#include<iostream>
#include<stdio.h>
using namespace std;
const int N=100010;
long n=0,h[N];
bool check(int e)
{for(int i=1;i<=n;i++){e=2*e-h[i];if(e>=1e5)return true;if(e<0)return false;}return true;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&h[i]);}int l=0,r=1e5;while(l<r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}printf("%d\n",r);}

题目:分巧克力蛋糕

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi​×Wi 的方格组成的长方形。为了公平起见，

小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;

2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 ,N,K (1≤N,K≤1e5)。

以下 N 行每行包含两个整数Hi​,Wi​ (1≤Hi​,Wi​≤1e5)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

示例

输入

2 10
6 5
5 6

输出

2

 

白话讲解:

有k个小朋友来家里,而我有N块巧克力,如何切出k个正方形,且每个正方形面积最大,输出边长

题解:

边越大则面积越大,但能分的块数就越少,所以我们要找到的是一个边最大,且块数等于k的边长

这题与上题的区别为,正方形的边长a不满足 a满足题意 比a大的都满足题意.但比a小的都满足题意,所以这题的区间为右半边为开区间,也即left=mid,right=mid-1.

check函数为wi/e*hi/e 这里可以理解为,巧克力总面积除以每一块巧克力的面积,即为块数,为什么是除/边长呢?向下取整.之后若>=k则说明满足题意返回即可,当所有巧克力切完还不满足,则返回false

代码实现:

#include <iostream>
using namespace std;
const int N=10010;
int h[N],w[N];
int n=0,k=0;
bool check(int e)
{int res=0;for(int i=0;i<n;i++){res+=(h[i]/e)*(w[i]/e);if(res>=k)return true;}return false;
}
int main()
{cin>>n>>k;for(int i=0;i<n;i++){cin>>h[i]>>w[i];}int l=1,r=1e5;while(l<r){int mid=l+r+1>>1;if(check(mid))l=mid;else r=mid-1;}printf("%d",l);return 0;
}

完结撒花：

🌈本篇博客的内容【分巧克力、机器人跳跃、数的范围】已经结束。

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！