高端网站设计哪家公司好,显示屏东莞网站建设,现在的网站内容区域做多宽,汉邦未来网站建设前言
众所周知蓝桥杯会暴力#xff0c;那么拿奖也是很轻松#xff0c;甚至拿省一#xff0c;有些题甚至直接用暴力就是对的#xff0c;二分查找就是暴力中常用的算法#xff0c;这篇文章就用蓝桥杯中的题目去介绍如何用二分查找去解题#xff0c;对于二分查找的基础知识…前言
众所周知蓝桥杯会暴力那么拿奖也是很轻松甚至拿省一有些题甚至直接用暴力就是对的二分查找就是暴力中常用的算法这篇文章就用蓝桥杯中的题目去介绍如何用二分查找去解题对于二分查找的基础知识我就不再多说了网上有很多也不难了解基础的就可以了
分巧克力
题目链接用户登录
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。为了公平起见
小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足 形状是正方形边长是整数; 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么
输入描述
第一行包含两个整数 N,KN,K (1≤N,K≤1051≤N,K≤105)。
以下 N 行每行包含两个整数 Hi,WiHi,Wi (1≤Hi,Wi≤1051≤Hi,Wi≤105)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出描述
输出切出的正方形巧克力最大可能的边长。
输入
2 10
6 5
5 6输出
2先看代码
#includebits/stdc.h
using namespace std;
long long h[100005],w[100005];
long long k,n;
bool check(int x)
{long long sum0;for(int i0;in;i){sum(h[i]/x)*(w[i]/x); //当正方形的长度是x时去遍历看这个x是否满足条件}if(sumk)return true;elsereturn false;
}
int main()
{cinnk;for(int i0;in;i){cinh[i]w[i];}long long max0;long long l1,r100000,mid; //r100000就是巧克力的长和宽的最大值然后在这个范围中找最大值while(lr){mid(lr)/2;if(check(mid)){maxmid;lmid1;}elsermid-1;}coutmax;return 0;
}
这道题二分查找就是再用暴力算法它给出了k的最大值就是100000,巧克力的长度和宽度最大也是100000数据比较小可以直接用暴力
冶炼金属
题目链接用户登录
题意
小蓝有一个神奇的炉子用于将普通金属 OO 冶炼成为一种特殊金属 XX。这个炉子有一个称作转换率的属性 VVVV 是一个正整数这意味着消耗 VV 个普通金属 OO 恰好可以冶炼出一个特殊金属 XX当普通金属 OO 的数目不足 VV 时无法继续冶炼。
现在给出了 NN 条冶炼记录每条记录中包含两个整数 AA 和 BB这表示本次投入了 AA 个普通金属 OO最终冶炼出了 BB 个特殊金属 XX。每条记录都是独立的这意味着上一次没消耗完的普通金属 OO 不会累加到下一次的冶炼当中。
根据这 NN 条冶炼记录请你推测出转换率 VV 的最小值和最大值分别可能是多少题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数 NN表示冶炼记录的数目。
接下来输入 NN 行每行两个整数 AA、BB含义如题目所述。
输出格式
输出两个整数分别表示 VV 可能的最小值和最大值中间用空格分开。
样例输入
3
75 3
53 2
59 2样例输出
20 25样例说明
当 V20V20 时有⌊7520⌋3⌊2075⌋3⌊5320⌋2⌊2053⌋2⌊5920⌋2⌊2059⌋2可以看到符合所有冶炼记录。
当 V25V25 时有⌊7525⌋3⌊2575⌋3⌊5325⌋2⌊2553⌋2⌊5925⌋2⌊2559⌋2可以看到符合所有冶炼记录。
且再也找不到比 2020 更小或者比 2525 更大的符合条件的 VV 值了。
提示
对于 3030% 的评测用例1≤N≤1021≤N≤102。
对于 6060% 的评测用例1≤N≤1031≤N≤103。
对于 100100% 的评测用例1≤N≤1041≤N≤1041≤B≤A≤1091≤B≤A≤109。
代码
#includebits/stdc.h#define rep(i, a, b) for(int i a; i b; i)using namespace std;
const int N 1e4 10;
int n;int get(int a, int b)
{int l 1, r 1e9 1;while(l r){int mid l r 1;if(a / mid b)r mid;else l mid 1;}return r;
}int main()
{cin n;int minv 1, maxv 1e9;int a, b;rep(i, 0, n){scanf(%d%d, a, b);//对于所有的集合取交集minv max(minv, get(a, b));maxv min(maxv, get(a, b - 1) - 1);}cout minv maxv;return 0;
}它这道题用二分查找是找到了这一中比较巧妙的方法这道题可以看我前一篇博客不用二分也可以爆破出来这道题就是一道找规律的题
以下是大佬用数学公式推出来的然后用二分查找
1.根据题目有以下公式推导 因为 ⌊A/V⌋B⌊A/V⌋B
有 BA/VB1BA/VB1
取倒数有 1/(B1)V/A1/B1/(B1)V/A1/B
两边同时乘AA: A/(B1)VA/BA/(B1)VA/B
2.这样区间左边取A/(B1)1A/(B1)1最大值右边取 A/BA/B最小值即可
