网站开发 怎样做费用结算,wordpress设置本地盘,在线设计头像,有诗意的设计公司名字二分查找算法
知识点
二分查找原理讲解在单调递增序列 a 中查找 x 或 x 的后继在单调递增序列 a 中查找 x 或 x 的前驱
二分查找算法讲解
枚举查找即顺序查找#xff0c; 实现原理是逐个比较数组 a[0:n-1] 中的元素#xff0c;直到找到元素 x 或搜索整个数组后确定 x 不在…二分查找算法
知识点
二分查找原理讲解在单调递增序列 a 中查找 x 或 x 的后继在单调递增序列 a 中查找 x 或 x 的前驱
二分查找算法讲解
枚举查找即顺序查找 实现原理是逐个比较数组 a[0:n-1] 中的元素直到找到元素 x 或搜索整个数组后确定 x 不在其中。最坏情况下需要比较 N 次时间复杂度是 O(n)属于线性阶算法。 而二分查找是一种折半查找方法。 该方法将 N 个元素分成大致相等的两部分选取中间元素与查找的元素进行比较。
如果相等则查找成功如果查找元素小于中间元素则在左半区继续查找如果查找元素大于中间元素则在右半区继续查找。 每次都将范围缩小至原来的一半因此时间复杂度是 O ( log 2 n ) O(\log_{2}n) O(log2n)。 需要注意的是二分查找的前提是数组有序一般是从小到大排列。 折半查找的基本思想 在有序表中low, high, lowhigh取中间记录即 a[(highlow)/2] 作为比较对象。若给定值与中间记录的关键码相等则查找成功。若给定值小于中间记录的关键码则在中间记录的左半区继续查找。若给定值大于中间记录的关键码则在中间记录的右半区继续查找。 不断重复上述过程直到查找成功或所查找的区域无记录查找失败。 二分查找的特征
答案具有单调性。二分答案的问题往往有固定的问法例如令最大值最小最小值最大求满足条件的最大小值等。 折半查找一般过程
Step 1:假设存在一个有序数组
下标[ 0 1 2 3 4 5 6 7 8 9 10 11 12 ]
数据[ 7 14 18 21 23 29 31 35 38 42 46 49 52 ]↑ ↑low0 high12mid(lowhigh)/2mid(012)/2mid6[mid]31 14所以选择左半部分操作此时令low不变highmid-15Step 2:下标[ 0 1 2 3 4 5 6 7 8 9 10 11 12 ]
数据[ 7 14 18 21 23 29 31 35 38 42 46 49 52 ]↑ ↑low0 high5mid(lowhigh)/2mid(06)/2mid3[mid]21 14所以选择左半部分操作此时令low不变highmid-12Step 3:下标[ 0 1 2 3 4 5 6 7 8 9 10 11 12 ]
数据[ 7 14 18 21 23 29 31 35 38 42 46 49 52 ]↑ ↑low0 high2mid(lowhigh)/2mid(02)/2mid1[mid]14 14 找到答案操作返回下标整数二分法常用算法模板
// 在单调递增序列a中查找x的数中最小的一个即x或x的后继
while (low high)
{int mid (low high) / 2;if (a[mid] x)high mid;elselow mid 1;
}// 在单调递增序列a中查找x的数中最大的一个即x或x的前驱
while (low high)
{int mid (low high 1) / 2; //向右1个以便于判断区间的时候落到右侧// int mid left (right - left) / 2;if (a[mid] x)low mid;elsehigh mid - 1;
}此处我们先分整数的二分查找法的常用模版关于实数的部分我们后面再讲。 为什么采用这一套代码的而不是采用查找等于的 X 是因为这样的适用范围更广当有 X 时这套代码就返回 X 的位置。如果没有 X就返回 x 的数中最大的一个或者 x 的数中最小的一个。 跳石头
【题目描述】 “跳石头比赛在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有n块岩石(不含起点和终点的岩石)。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。 为了提高比赛难度组委会计划移走些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走m块岩石(不能移走起点和终点的岩石) 【输入描述】 输入文件第一行包含三个整数LNM分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。 接下来 N行每行一个整数第 i行的整数 Di(0DiL)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。 其中0≤M≤N≤5x1041≤L≤109 【输出描述】 输出只包含一个整数即最短跳跃距离的最大值。
题目解析
二分法套路题最小值最大化最大值最小化 在n块岩石中移走m个石头有很多种移动方法 在第i种移动方法中剩下的石头之间的距离有一个最小距离ai. 在所有移动方法的最小距离ai中问最大的ai是多少 在所有可能的最小值中找最大的那个就是最小值最大化
在单调递增的序列中找到满足某个条件的最大的那个值
暴力法找所有的组合在n块岩石中选m个石头的组合情况太多超时二分思路不找搬走石头的组合而是给出一个距离d检查能不能搬走m块石头而得到最短距离d。把所有的d都试一遍肯定能找到一个最短的d用二分法找这个d
最短距离ai最小可以取到0最大可以取到L不管用什么方法ai一定是这个区间上的一个数 这个区间是一个递增的有序的 二分这个区间找到一个ai检查这个ai是不是符合题意是不是能通过n块岩石中移走m块岩石能构造出最短距离是ai的这么一种情况 如何判断能否通过n块石头中一走m块石头来实现 比如说现在要找的ai是3有5块石头它们之间的距离是5342显然534满足条件但是2不满足所以要移走第四块石头变成536可以通过这样的方法来判断是否要移走某块石头 满足了3以后因为要找最大的所以解下来判断4这一组石头里的3就不符合了移走第二块石头变成86这样就需要移走两块石头 如果m2的话就满足条件如果m1就不满足 所以m1的话ai就只能是3m2的话可以是4 如果是用暴力法去找的话就是从1开始一直枚举到L1~L是一个有序的枚举所以可以通过二分去做 1~L。找mid看这个mid能不能通过移走m块来实现可以的话就在右边的区间继续去找不能移走的话就从左区间开始找
代码
#include cstdio
int len, n, m;
int stone[50005];
bool check(int d) //检查距离d是否合适
{int num 0; //num记录搬走石头的数量int pos 0; //当前站立的石头for (int i 1; i n; i ){if (stone[i]-pos d)num; //第i块石头可以搬走elsepos stone[i]; //第i块石头不能搬走}if (num m)return true; //要移动的石头比m少满足条件elsereturn false; //要移动的石头比m多不满足条件
}int main()
{scanf(%d%d%d, len, n, m);for (int i 1; i n; i ){scanf(%d, stone[i]);}int L 0, R len, mid;while (L R){mid (L R 1) / 2;//查找满足条件的最大的那个值所以向右贪心if (check(mid)){L mid; //满足条件说明mid小了调大一点}elseR mid - 1; //不满足条件说明mid大了调小一点}printf (%d\n, L);return 0;
}M 次方根
题目描述: 小 A 最近在学高等数学他发现了一道题求三次根号下27。现在已知小 A 开始计算1 的三次方得12 的三次方得83 的三次方得27然后他很高兴的填上了3。 接着他要求5次根号下164。然后他开始1 的三次方得12 的三次方得83 的三次方得27… 直到他算到了秃头也没有找到答案。 这时一旁的小 B 看不下去了说这题答案又不是个整数。小 A 震惊原来如此。作为程序高手的小 A打算设计一个程序用于求解M次根下N的值。 但是由于要考虑精度范围答案必须要保留7位小数连三次根号下27都要掰手指的小 A 又怎么会设计呢。请你帮小 A 设计一个程序用于求解 M 次根号N。 数据范围 1≤N≤1e5 1≤M≤100 M N 要求输入:
输入描述:
第一行输入整数 N 和 M数据间用空格隔开。要求输出
输出描述:
输出一个整数并保留 7 位小数。样例:
输入样例
27 3
输出样例
3.000000运行限制:
最大运行时间1s
最大运行内存: 256M
注意
1. 请严格按要求输出不要画蛇添足地打印类似“请您输入…” 的多余内容。
2. 不要调用依赖于编译环境或操作系统的特殊函数。
3. 所有依赖的函数必须明确地在源文件中。
4. 不能通过工程设置而省略常用头文件。题目分析
根据前面的知识我们要找到一个具有单调性的数列去二分。这个题的关键是我们要去二分什么这里可以二分的是 a^M 中的 a所以我们要先想办法设计出用于处理实数二分的代码。 这里给大家两个模板都可以大家选择一个使用即可
//模版一实数域二分设置eps法//令 eps 为小于题目精度一个数即可。比如题目说保留4位小数0.0001 这种的。那么 eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。//一般为了保证精度我们选取精度/100 的那个小数即设置 eps 0.0001/100 1e-6while (l eps r) //l加上这个精度r就继续二分
//如果不小于r就说明l-reps代表这两个数之间的精度差距不会超过0.0001代表找到这个值了
{double mid (l r) / 2;if (pd(mid))r mid;elsel mid;
}//模版二实数域二分规定循环次数法
//通过循环一定次数达到精度要求这个一般 log_2 N 精度即可。N 为循环次数在不超过时间复杂度的情况下可以选择给 N 乘一个系数使得精度更高。
//为什么循环100次一定可以二分是每次除以2除100次2也就是做100次log_2n1024是10次。10^6约20次10^9约30次所以100次一定可以满足for (int i 0; i 100; i)
{double mid (l r) / 2;if (pd(mid))r mid;elsel mid;
}模板讲完了然后我们就要考虑判定条件了怎样判定是否存在满足大于平均值的区间。当然这个题你可以使用语言中自带开方软件但是我们还是联系一下实数的二分代码。 关于判定条件我们应该设计一个代码用于比较 a^m 和 N 的大小关系。 在我们代码中
if (pd(mid))r mid;
elsel mid;pd 成功的情况一定是 pd 的mid 符合条件且小于 mid 的一定符合条件。因此我们要在大于mid 中继续查找找到更大的mid。 所以我们可以设计出如下判定条件:
double pd(double a,int m)
{double c1;while(m0) //计算a的m次方{cc*a;m--;}if(cn) return true;elsereturn false;
}代码解答
#include cstdio
#include iostream
#includeiomanip //用于浮点数输出
using namespace std;double n,l,r,mid;
double eps1e-8;bool pd(double a,int m)
{double c1;while(m0) {cc*a;m--;}if(cn) //return true;elsereturn false;
}int main()
{int m;cinnm;
//设置二分边界l0,rn;//实数二分while (l eps r){double mid (l r) / 2;if (pd(mid,m))r mid;elsel mid;}cout fixed setprecision(7) l;//一般使用print//printf(%x.yf,n)//其中X是固定整数长度小数点前的整数位数不够会在前面补0//y是保留小数位数不够补零//printf(%.7f,l);return 0;
}分巧克力
2017 年省赛真题链接。 题目描述: 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N 块巧克力其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见 小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足
形状是正方形边长是整数;大小相同; 例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。 当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么 输入描述: 第一行包含两个整数 N,K (1≤N,K≤10^5)。 以下 N 行每行包含两个整数 Hi,Wi (1≤Hi,Wi≤10^5)。 输入保证每位小朋友至少能获得一块 1x1 的巧克力。 输出描述: 输出切出的正方形巧克力最大可能的边长。 输入输出样例: 示例: 输入 2 10 6 5 5 6输出 2运行限制:
最大运行时间2s最大运行内存: 256M 注意
请严格按要求输出不要画蛇添足地打印类似“请您输入…”的多余内容。不要调用依赖于编译环境或操作系统的特殊函数。所有依赖的函数必须明确地在源文件中不能通过工程设置而省略常用头文件。
题目分析
简单思路边长的最大规模为 100000我们可以枚举出所有的情况。按从大到小的顺序进行切割直到找到满足要求的巧克力边长。 在判断边长是否满足条件时求一块长方形h∗w最多被分成的正方形len∗len巧克力个数为 cnt(h/len)∗(w/len) 但是使用朴素算法枚举时间复杂度O(n)∗O(n)O(n^2) 会超时所以改用 2 分查找法这找到符合要求的最大的一个。 即用在单调递增序列 a 中查找 x 的数中最大的一个即 x 或 x 的前驱即可原本这里的条件是 x 我们将其换成验证即可。
代码解答
#includebits/stdc.husing namespace std;
const int MAXN100010;
int n,k;
int h[MAXN],w[MAXN];bool pd(int l)
{int sum0;for(int i0; in; i){sum(h[i]/l)*(w[i]/l);if(sumk){return true;}}return false;
}int main()
{cinnk;for(int i0; in; i)cinh[i]w[i];//找到二分查找的上界int high0;for(int i0; in; i){highmax(high,h[i]);highmax(high,w[i]);}// 二分下届由题意可得至少为1int low1;// 由于本题目就是求符合要求的Mid 值所以要将mid定义在二分查找外边int mid0;while(lowhigh){mid (low high1) / 2;if(pd(mid))lowmid;elsehigh mid - 1;// coutlow highendl;}//因为lowhigh所以输出哪一个都一样coutlow;return 0;
}
