P2440木材加工

题解 OI笔记

题目链接

最最最最基本的二分题！

Noip2018之前做道二分题，万一考到了呢？（望我这篇题解对想了解二分的人有帮助）

话归正传：

咳，这是一道十分基本的二分答案，可以当做模板来用

二分基本做法：

设置一个左端点和右端点，$mid$为中间值，如果$flag$比中间值小，则右端点转为$mid$，否则左端点转为$mid$

很容易想到到，只要我们不断地二分下去，正确答案迟早会得到的。

这里提供一种二分模板（仅供参考，二分有好多种写法的）：

int l = 0 , r = 210000000 ;
while( l < r - 1 ){  //这里要注意一下，l必须要<r-1，否则会陷入死循环
    int mid = l + r >> 1 ;
    if( mid >= flag ) r = mid ;
    else l = mid ;
}

为什么 $l<r-1$ ?

我们可以手动模拟一下：

1.我们假设$ans=3,l=2,r=4$ ; 那么$mid=2+4>>1=3;mid>=ans,$则$r=mid=3$
2.再来一次，$mid=2+3>>1=2;mid<ans,$则$l = mid = 2$

很明显，对于在第二步之后，$l$一直小于$r$，并且$l$和$r$的值在第二步之后一直未发生改变，这样我们就会陷入死循环，所以我们需要$l<r-1$，在第一步时我们就已经得到正确答案，那时$l = 2 , r = 3$，不满足循环条件，跳出，$r$即为正确答案.

另一种写法:

while( l <= r ){
    int mid = l + r >> 1 ;
    if( mid >= flag ){
        ans = mid ;
        r = mid - 1 ;
    } 
    else l = mid + 1 ;
}

这里使用$r$和$l$各加一或减一来避免死循环，要注意的是这里用$ans$来储存答案，因为$r$和$l$对应的$mid$值有所改变

问题来了，那么对于这道题我们应该怎么去做呢？

首先题目给了我们一个要求截成的$k$段，那么我们可以去二分这个$k$，首先我们的$mid$要满足$a[i]/mid$之和要等于$k$，如果大于$k$，则表明我们的$mid$取值小了，$l=mid$，否则$r=mid$（PS：这里与上面的板子有所不同，其实$l$和$r$的转换是应该根据实际情况去判断的）

于是二分思想有了，接下来我们去找端点

端点这个问题也是值得我们注意的，首先题目上表明木材可以剩余和丢弃，那么假如我们有一段木头贼长，仅凭他一己之力就可以去截出最长且满足$k$段，那么我们其他的全可以丢弃，就截这一段就可以了（这是一个坑点，这个题的数据点3完美的坑到了我），于是我们的端点$r$初始并不是木材中的最大值，而应设为一个极大的数，只要超过题目中木材长度最大就好了。

emmm，还有判断函数，其实就要把$a[i]/mid$加起来，再返回回去就好啦（详细见附码）

于是我们有了端点、二分思想、判断函数、还有板子，便可以愉快的AC啦~~qwq

附code：

#include <cstdio>
int n , k , a[100500] ;
int judge( int temp ){
    int sum = 0 ;
    for( int i = 1 ; i <= n ; i ++ ) sum += a[i] / temp ;
    return sum ;
}
int main(){
    scanf( "%d%d" , &n , &k ) ;
    for( int i = 1 ; i <= n ; i ++ ){
        scanf( "%d" , &a[i] ) ;
    } 
    int l = 0 , r = 210000000 ;
    while( l < r - 1 ){ 
        int mid = ( l + r ) >> 1 ;
        if( judge( mid ) >= k ) l = mid ;
        else r = mid ;
    }
    printf( "%d" , l ) ;
    return 0 ; 
}

趁热打铁

看到代码觉得很简单的有木有？

我突然觉得这道题是伪普及