题解 P2440 【木材加工】

· · 题解

蒟蒻的题解

一道二分答案例题。

首先看题，题目中有这样一段话：

即求最小的最大，所以用二分答案

注意：请忽略以下代码中奇奇怪怪的变量名

不要抄题解哦~~（你已经被Hzc警告了）

二分答案

在知道这是什么前，运用这种算法的题都有一个明显特征：

    使最大……最小
    使最小……最大

总之就是求min(max)或max(min)

Q：说了半天，这是啥啊啊啊啊啊啊啊啊啊啊啊啊

这个吗……

二分答案跟二分查找类似，就是在一个答案区间内二分枚举可能的答案

二分答案的答案区间必须具有单调性（或者你可以说有序性）

单调性，即 当i>j时，a[ i ]>a[ j ] 。我们简单举个例子：

int a[6]={0,1,5,4,2,3};

这时就不能运用二分答案

非常明显，a[ 3 ]==4 > a[ 4 ]==5 但 3 < 4 , 所以,为了运用二分答案法，我们要对其进行排序，一般直接用sort即可

这么说来，二分答案的板子已经出来了：

int l=1,r=n,ans;
while(l<=r){
    int mid=(l+r)>>1 //位运算加速，等价于(l+r)/2
    if(check(mid)){//判断当前ans比mid大（或相等）还是小
        update(ans);//比mid大（或相等），ans更新 
        l=mid+1;//往上缩小范围。但注意！不加1可能跑成死循环(即一直l==r） 
    }else r=mid-1;//缩小范围，注意同上 
}

死循环就是说若l==r，则mid==l==r，若不加1减1则l==r不变，则TLE……

对于check函数，根据题目编写

回到本题

左端点l=0没得说，但右端点r就有点……

所以，如果要剩下木头，为了满足最小的最大要求，长度大的肯定不能剩，只能剩下长度小的木头

so，r=maxlen，在读入时用max函数直接计算

然后就是关键的check函数了, 直接暴力取段数：

bool check(int rp){//rp即为当前mid所对应长度 
    hzc=0;//初始化 
    for(int i=1;i<=n;i++)hzc+=wood[i]/rp;//wood[i]/rp表达木头i在每段长rp的情况下能分的段数
    /*注意：你没法把几根木头合到一起，所以每根木头的段数单独算*/ 
    if(hzc>=k)return true;//符合（或过于符合）题意，返回真 
    return false;//不符合，返回假 
}

二分部分，完全可以套刚刚的板子，只是要个性化处理update：

    while(l<=r){
        mid=l+r>>1;
        if(check(mid)==true){
            ans=max(ans,mid);//按题目要求取最大值
            l=mid+1;
        }else r=mid-1;
    }

以下直接上代码（关键部分注释往上）：

#include<con>
using namespace std;
int l,r,mid;
int n,k,wood[100001];//wood存木头长度
int up,hzc;
int ans;
bool check(int rp){
    hzc=0;
    for(int i=1;i<=n;i++)hzc+=wood[i]/rp;
    if(hzc>=k)return true;
    return false;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&wood[i]);
        up=max(up,wood[i]);//右端点
    }
    l=1;
    r=up;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)==true){
            ans=max(ans,mid);
            l=mid+1;
        }else r=mid-1;
    }
    printf("%d",ans);
}