做网站用什么压缩代码和图片,WordPress主题后门检测,产品网站怎么做,微信怎么开店铺小程序本文用于记录个人算法竞赛学习#xff0c;仅供参考 一.二分算法
二分算法一般用于具有二段性的问题#xff0c;数据不一定具有单调性#xff0c;所以单调可二分#xff0c;可二分不一定就要单调。
二.整数二分
1. 模板一#xff1a;将区间[l, r]划分为[l, mid] 和 [mid… 本文用于记录个人算法竞赛学习仅供参考 一.二分算法
二分算法一般用于具有二段性的问题数据不一定具有单调性所以单调可二分可二分不一定就要单调。
二.整数二分
1. 模板一将区间[l, r]划分为[l, mid] 和 [mid 1, r], mid属于左区间更新操作为r mid 和 l mid 1; 计算mid 向下取整。
int bsearch_1(int l, int r)
{while (l r){int mid l r 1;//check函数是处理逻辑if (check(mid))r mid;elsel mid 1;}//最后l和r都指向同一个数返回哪个都可以return l;
}2.模板二将区间[l, r]划分为[l ,mid - 1] 和 [mid 1, r], mid 属于右区间更新操作为r mid - 1 和 l mid; 计算mid时要1向上取整避免死循环。
mid (l r 1) 1避免死循环的逻辑是假设剩余最后两个数mid l r 1那么mid l倘若mid对应值不是目标值,那么l mid,这就形成闭环了所以需要向上去取整。
int bsearch_2(int l, int r)
{while (l r){int mid (l r 1) 1;//check函数是处理逻辑if (check(mid))l mid;elser mid - 1;}return l;
}
三.浮点数二分
double bsearch_3(double l, double r)
{// eps 表示精度取决于题目对精度的要求const double eps 1e-6; while (r - l eps){double mid (l r) / 2;if (check(mid)) r mid;else l mid;}return l;
}
四.题目
1.浮点数二分 int main()
{int n;cin n;//由于c浮点数存在精确度问题当题目要求精确到几位数时一般esp再往后取多两位double esp 1e-8;double l 0, r n;while (r - l esp){double mid (l r) / 2;if (mid * mid n)r mid;elsel mid;}printf(%lf\n, l);return 0;
} 2.整数二分
P8647 [蓝桥杯 2017 省 AB] 分巧克力 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 根据题意得需要找到符合条件的最大边长假设这个边长是x那么小于x的边长可以按要求分给每个小盆友不是最大边长大于x的边长不可能按要求平均分给小盆友可以看出具有二段性可以用二分所以边长可以抽象成一条数轴进而二分求得最大值。 #include iostream
#include cstdio
using namespace std;typedef long long LL;
int N 100010;
int n, k;
int H[100010], W[100010];bool check(int mid)
{//统计饼干个数LL cnt 0;for(int i 0; i n; i){cnt (LL)(H[i] / mid) * (W[i] / mid);}if(cnt k)return true;elsereturn false;
}int main()
{scanf(%d %d,n, k);for(int i 0; i n; i){scanf(%d %d,H[i],W[i]);}int l 0, r 100010;while(l r){int mid l r 1 1;if(check(mid))l mid;elser mid - 1;}printf(%d\n,r);return 0;
}
