政务网站建设经验交流发言,wordpress apache模块,太仓网站制作书生,网页设计与制作教程第四版答案Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … 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
#includeiostream
using namespace std;
const int N100010;
int n,m;
int q[N];
int main()
{scanf(%d%d,n/*正数组长度*/,m/*查询个数*/);for(int i0;in;i){scanf(%d,q[i]);}while(m--){int x0;scanf(%d,x);int left0,rightn-1;while(leftright){int mid(leftright)1;if(q[mid]x)rightmid;else leftmid1;}if(q[left]!x)cout-1 -1 endl;else{coutleft ;int left0,rightn-1;while(leftright){int mid(leftright1)1;if(q[mid]x)leftmid;else rightmid-1;}coutleftendl;}}return 0;
} 题目:机器人跳跃问题 机器人正在玩一个古老的基于 DOS 的游戏。 游戏中有 N1 座建筑——从 00 到 N 编号从左到右排列。 编号为 00 的建筑高度为 00 个单位编号为 i 的建筑高度为 H(i) 个单位。 起初机器人在编号为 00 的建筑处。 每一步它跳到下一个右边建筑。 假设机器人在第 k个建筑且它现在的能量值是 E下一步它将跳到第 k1 个建筑。 如果 H(k1)E那么机器人就失去 H(k1)−E的能量值否则它将得到 E−H(k1)的能量值。 游戏目标是到达第 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)的能量,要求跳跃中能量不能为负
题解:
分析两个扣除能量的规则就可以发现,不论高低与否,能量E2E-h(i) ,也就是能量一直都是这样改变的,判断是否能用二分来搜寻答案最重要的就是判定其是否满足递增的条件(必要不充分),
当找到一个满足条件的E之后,大于E的情况下是都能跳跃过去.所以我们用二分来做.
int的数据范围最大为1e9,而观察这题题设范围,当h(i)足够小的时候,E2E,有可能爆int,所以我们推断,当Eh(i)max时,此时表达式为EEh(i)max-h(i) h(i)无限小,即可忽略不计,所以当Eh(i)max时,即可表示其可跳跃过之后所有的格子.
也可以理解为,当我跳到最高点时,之后都是在增加能量,而不是减少,所以即可判定一定能跳过
另外,刚刚说过了E的条件都满足题解,所以这里的二分为leftmid1 rightmid
不懂我在说什么的uu可以回顾下二分
check函数为:模拟跳跃每一次
代码实现:
#includeiostream
#includestdio.h
using namespace std;
const int N100010;
long n0,h[N];
bool check(int e)
{for(int i1;in;i){e2*e-h[i];if(e1e5)return true;if(e0)return false;}return true;
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,h[i]);}int l0,r1e5;while(lr){int midlr1;if(check(mid))rmid;else lmid1;}printf(%d\n,r);} 题目:分巧克力蛋糕 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N 块巧克力其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见 小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足 形状是正方形边长是整数; 大小相同; 例如一块 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小的都满足题意,所以这题的区间为右半边为开区间,也即leftmid,rightmid-1.
check函数为wi/e*hi/e 这里可以理解为,巧克力总面积除以每一块巧克力的面积,即为块数,为什么是除/边长呢?向下取整.之后若k则说明满足题意返回即可,当所有巧克力切完还不满足,则返回false
代码实现:
#include iostream
using namespace std;
const int N10010;
int h[N],w[N];
int n0,k0;
bool check(int e)
{int res0;for(int i0;in;i){res(h[i]/e)*(w[i]/e);if(resk)return true;}return false;
}
int main()
{cinnk;for(int i0;in;i){cinh[i]w[i];}int l1,r1e5;while(lr){int midlr11;if(check(mid))lmid;else rmid-1;}printf(%d,l);return 0;
}
完结撒花 本篇博客的内容【分巧克力、机器人跳跃、数的范围】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
