首页 > 代码库 > 木材加工（裸二分题）（附二分算法粗略介绍）
木材加工（裸二分题）（附二分算法粗略介绍）
看到旁边的学弟也在做二分，就手贱2分钟打了一道奇（sha）特（bi）二分题。
原题传送门
好吧，做这道题是为了给新手一个教程
首先我们聊聊二分。
二分利用的也是分治思想
不懂分治思想的可以看看我归并做的那道火柴排队。
传送门
首先要了解一下二分的性质（也就是什么题目要用二分来写、）
我们假设一个题目，如果一个数a能够满足题意，并且U=[数值最小值/数值最大值（看题意）~a]中的数就一定能够满足题意。
那么这道题目就能用来二分。。
或者说一道题目的解的解集为U，如0<i<a;题目的范围是0<i<l；已知l>a;要我们求a的值
那么这道题目就能用来二分。、
好吧，好想还是很复杂。
还是贴代码比较稳妥。
简单一句话来说，就是答案具有单调性的题目可以用来二分。。（单调性等我开始做单调队列的时候再来填坑。。）
下面贴原题代码。。主程序相当于模板啦233~
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,k,a[10001]; bool check(int x) { int ans=0; for(int i=1;i<=n;i++) ans+=a[i]/x; return ans>=k; } int main(){ int maxn=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(maxn<a[i])maxn=a[i]; } int l=1,r=maxn; int ans=0; while(l<=r) { int mid=(l+r)>>1; if(!check(mid))r=mid-1; else ans=mid,l=mid+1; } printf("%d\n",ans); }
木材加工（裸二分题）（附二分算法粗略介绍）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。