木材切割

开始进行专项练习，今天是二分答案。

这是第一题。

原题链接：https://www.luogu.org/problem/show?pid=2440#sub

题意要求我们把木材切割成很多段，使得这个短段尽量的长。

我们切割的段肯定是在[ 0,max{ wood [ i ] } ]中，满足二分的有界性。

由题意显然单调，满足单调性。所以可以使用二分答案求解。

我们在读入的时候预处理出上边界r，特别注意下边界l是0不是1否则会RE第四点。

check函数也很好实现。以当前的答案x为标准去切割这些木材。枚举所有木材，对于每一段木材其能分割的段数最大是wood[i] / x，设一个累加器cnt记录这个值，用一个ans变量记录答案。

如果发现能切够k段则去右半部分找更大的解，如果发现切不够k段就去左边找可行解。

参考代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 #define maxn 100005
 6 #define maxl 100000005
 7 using namespace std;
 8 inline int read(){
 9     int num = 0;
10     char c;
11     bool flag = false;
12     while ((c = getchar()) == ' ' || c == '
' || c == '
');
13     if (c == '-')
14         flag = true;
15     else
16         num = c - '0';
17     while (isdigit(c = getchar()))
18         num = num * 10 + c - '0';
19     return (flag ? -1 : 1) * num;
20 }
21 int wood[maxn];
22 int n,k,ans;
23 
24 bool check(int x){
25     int cnt = 0;
26     if (x==0)
27         return false;
28     for (register int i=1;i<=n;i++)
29         cnt += wood[i] / x;
30     if (cnt >= k){
31         ans = max(ans,x);
32         return true;
33     }
34 
35     else
36         return false;
37 
38 }
39 int main(){
40     int l = 0,r = maxl;
41     n = read();k = read();
42     for (register int i=1;i<=n;i++){
43         wood[i] = read();
44         r = max(r,wood[i]);
45     }
46     while (l < r){
47         int mid = (l+r) >> 1;
48         if (check(mid))
49             l = mid + 1;
50         else
51             r = mid;
52     }
53     printf("%d
",ans);
54     return 0;
55 }