大连科技学院官方网站的建设与放云南科技有限公司

当前位置： 首页 > news >正文

大连科技学院官方网站的建设与放,云南科技有限公司,桐庐住房和城乡建设局 网站,西宁专业制作网站#x1f63d;PREFACE#x1f381;欢迎各位→点赞#x1f44d; 收藏⭐ 评论#x1f4dd;#x1f4e2;系列专栏#xff1a;算法经典题集#x1f50a;本专栏涉及到的知识点或者题目是算法专栏的补充与应用#x1f4aa;种一棵树最好是十年前其次是现在二分整数二分机器人…PREFACE欢迎各位→点赞 收藏⭐ 评论系列专栏算法经典题集本专栏涉及到的知识点或者题目是算法专栏的补充与应用种一棵树最好是十年前其次是现在二分整数二分机器人跳跃问题机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N1 座建筑——从 0 到 N 编号从左到右排列。编号为 0 的建筑高度为 0 个单位编号为 ii 的建筑高度为 H(i) 个单位。起初机器人在编号为 0 的建筑处。每一步它跳到下一个右边建筑。假设机器人在第 kk 个建筑且它现在的能量值是 EE下一步它将跳到第 k1k1 个建筑。如果 H(k1)E那么机器人就失去 H(k1)−E 的能量值否则它将得到 E−H(k1)的能量值。游戏目标是到达第 N 个建筑在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏才可以保证成功完成游戏输入格式第一行输入整数 N。第二行是 N 个空格分隔的整数H(1),H(2),…,H(N)代表建筑物的高度。输出格式输出一个整数表示所需的最少单位的初始能量值上取整后的结果。数据范围1≤N,H(i)≤10^5,输入样例153 4 3 2 4输出样例14输入样例234 4 4输出样例24输入样例331 6 4输出样例33#include bits/stdc.h using namespace std; const int N 1e5 10; int n, h[N];bool check(int e) {for (int i 1; i n; i){e e * 2 - h[i];if (e 1e5) return true;if (e 0) return false;}return true; }int main() {cin n;for (int i 1; i n; i) cin h[i];int l 0, r 1e5;while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}cout r endl;return 0; } 【注意点】为什么该题可以用二分做呢 因为题设条件满足单调性并不是说二分就只能解决单调性非单调性二分也能做关于代码的11行是怎么来的能否去掉11行的由来是源于数学归纳法的证明它有两个作用一是加快代码运行速度二是避免出现越界。如果把第十一行去掉的话就要把e的类型改成double。分巧克力儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足形状是正方形边长是整数大小相同例如一块 6×5 的巧克力可以切出 6 块 2×2的巧克力或者 2 块 3×3的巧克力。当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么输入格式第一行包含两个整数 N 和 K。以下 N 行每行包含两个整数 Hi 和 Wi。输入保证每位小朋友至少能获得一块 1×1 的巧克力。输出格式输出切出的正方形巧克力最大可能的边长。数据范围1≤N,K≤10^51≤Hi,Wi≤10^5输入样例2 106 55 6输出样例2分析通过观察我们发现巧克力最后分成的总块数k和边长x具有一定关系当x越大我们最终分得的小巧克力块数k就越小。边长的大小与最终分得的小巧克力块数k成反比关系。既然我们最终要求的答案x恰好和k有关并且答案所在的区间又刚好可以由k一分为二成两种不同的性质因此本道题可以使用二分k就是我们要找的二分边界,左边的性质我们可以描述为cheak(x)≥k也就是说左边区间内的边长所分得的小巧克力总块数要大于等于题目要求的块数因此我们可以由此更新左端点使得答案区间向右边缩小这样不仅可以求得更大的边长x也可以找到恰好满足题意的k。这样我们的问题就得到了进一步简化变成了如何设计cheak()函数使得cheak(mid)可以刚好满足边界k的左边区间性质这样我们便可以顺理成章的更新左端点使得整个二分向右查找最总找到我们所需要的答案x。#include iostream using namespace std;int const N 100010; int w[N], h[N];//存储长、宽 int n, k;bool check(int a) {int num 0;//记录分成长度为 a 的巧克力数量for (int i 0; i n; i){num (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量if (num 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;//小巧克力数量边长一定在 1 – 100000 之间while (l r)//二分小巧克力边长范围找到符合要求的最大值{int mid l (r - l 1 1);//因为l mid 所以 mid 取 l r 1 1,为了防止加和越界改写成 l (r - l 1 1)if (check(mid)) l mid;else r mid - 1;}cout r endl;return 0; }跳石头这是一道典型的二分套路题“最小值最大化”类似题还有“最大值最小化”。什么是“最小值最大化”呢在所有可能的最小值中查找最大的那个值#include bits/stdc.h using namespace std; const int N 5e410; int len,n,m; int stone[N]; bool check(int d)//检查距离d是否合适 {int num,pos0;//num记录搬走岩石的数量 for(int i1;in;i)//当前站立的岩石 {if(stone[i]-posd) num;//第i块岩石可以搬走 else posstone[i];//第i块岩石不能搬走 }if(numm) return true;//要移动的岩石比m少,满足条件 else return false;//要移动的岩石比m多,不满足条件 }int main() {cinlennm;for(int i1;in;i) cinstone[i];int l0,rlen;while(lr){int midlr11;if(check(mid)) lmid;//满足条件,说明mid小了,调大一点 else rmid-1;//不满足条件,说明mid大了,调小一点 }coutrendl;return 0; }实数二分一元三次方程求解暴力解法判断一个数是否为解的方法如果函数值是连续变化的且函数值在解的两边分别是大于0和小于0的则解必然在它们中间。#include bits/stdc.h using namespace std; double a,b,c,d; double y(double x) {return a*x*x*xb*x*xc*xd; } int main() {cinabcd;for(double i-100;i100;i0.01){//写法一double ji0.01;double y1y(i),y2y(j);if(y1*y20) printf(%.2lf ,(ij)/2);//写法二if(abs(y(i))1e-6) printf(%.2lf ,i);}return 0; }二分#include bits/stdc.h using namespace std; double a,b,c,d; double y(double x) {return a*x*x*xb*x*xc*xd; } int main() {cinabcd;for(int i-100;i100;i)//题设条件给了两个根绝对值大于等于1,分200个小区间 {double lefti,righti1;//题设条件给了两个根绝对值大于等于1double y1y(left),y2y(right);if(y10) printf(%.2lf ,left);//判断左端点 if(y1*y20)//小区间内有根 {for(int j0;j100;j)//在小区间内二分 {double mid(leftright)/2;if(y(mid)*y(right)0)leftmid;elserightmid;}printf(%.2lf ,right);} }return 0; }