A6 二分答案 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P2440 ↗

题目描述

木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。请求出 $l$ 的最大值。

确保长度都是正整数。

例如有两根原木长度分别为 $11$ 和 $21$ ，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$ 。

输入格式

第一行是两个正整数 $n,k$ ，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$ ，表示一根原木的长度。

输出格式

仅一行，即 $l$ 的最大值。

如果连 $\text{1cm}$ 长的小段都切不出来，输出 0。

输入输出样例

输入 #1

plaintext

输出 #1

plaintext

对于 $100\%$ 的数据，有 $1\le n\le 10^5$ ， $1\le k\le 10^8$ ， $1\le L_i\le 10^8(i\in[1,n])$ 。

算法解析#

二分答案就是说用二分的方法枚举答案。

我现在在一堆木头中找最长的，我可以用一下方法：

最找到可行范围内最中间的数,用 check函数判断他是否可行

原理是：长度为 len 的情况下如果可以分到的段数比 k 多，返回true,否则返回 false

时间复杂度O( $nlog(max(L_i))$ )

Python代码实现#

def check(x):
    y = 0
    for i in range(1, n + 1):
        y += a[i] // x
    return y >= k

def find():
    l = 0
    r = int(1e8 + 1)
    while l + 1 < r:
        mid = (l + r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    return l
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
a.insert(0, 0)
print(find())

python

C++代码实现#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 100005;
int n, k, a[N];

bool check(int x){
  LL y=0; //段数
  for(int i=1;i<=n;i++) y+=a[i]/x;
  return y>=k; //x小,y大
}
int find(){
  int l=0, r=1e8+1;
  while(l+1<r){
    int mid=l+r>>1;
    if(check(mid)) l=mid; //最大化
    else r=mid;
  }
  return l;
}
int main(){
  scanf("%d%d",&n,&k);
  for(int i=1; i<=n; i++)scanf("%d",&a[i]);
  printf("%d\n",find());
  return 0;
}