首页 > 代码库 > 木材加工(裸二分题)(附二分算法粗略介绍)

木材加工(裸二分题)(附二分算法粗略介绍)

看到旁边的学弟也在做二分,就手贱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);
} 

 

木材加工(裸二分题)(附二分算法粗略介绍)