题解 | 华华给月月准备礼物

考虑二分答案，如果没有看出来是二分答案，细读题目发现其实题目的说明中有暗示。答案显然满足单调性，ans在小于等于某个值的时候都是符合题意的(切出来的木棍数>=k)，大于这个值的时候就不符合题意了，故可以二分。因此二分答案思路具体来说是：

1.读入数据

2.二分枚举答案

初始化l为可能的最小值(显然0是可能的最小值)，r为可能的最大值(题目Li和K最大都是1E9，我们就取1E9)

选取合适的二分模板，参考代码如下

int l = 0,r = 1E9;
while(l < r){
  int mid = (l+r+1)/2;
  
  if(check(mid)){
    r = mid;
  }else{
    l = mid-1;
  }
}

3.实现比较的check函数

要计算出当前二分枚举到的mid可以切出多少根木棍

考虑对于每个L[i]，最多可以切出floor(L[i]/mid)根木棍，其中floor表示下取整，使用cnt变量累加所有的情况

统计结束后判断cnt与k的关系，若cnt >= k，下一次二分往右查找，反之则下一次二分往左查找

特别地，我们会发现，如果mid取0，此时的check函数中存在L[i]/mid的操作，会出现浮点数运算错误，因此我们要特判mid=0的情况，此时下一次应该往左找即r = mid-1。（虽然题目没有卡这种情况，该除以0的特判可以加在二分模板的if判断上）

check函数的参考代码如下

auto check = [&](int x){
  int cnt = 0;
  for(int i = 0; i < n; i++){
    cnt += L[i]/x;
  }
  return cnt >= k;
};

4.二分结束输出答案

该二分模板结束后，l会等于r，因此输出l或者输出r都是对的

综上，总的时间复杂度为O(n*log(1E9))，数据量n最大为2E5，可以通过

整体参考代码如下

#include <iostream>
#include <vector>

void solve(){
  int n,k;
  std::cin >> n >> k;

  std::vector<int> L(n);
  for(int i = 0; i < n; i++){
    std::cin >> L[i];
  }

  auto check = [&](int x){
    int cnt = 0;
    for(int i = 0; i < n; i++){
      cnt += L[i]/x;
    }
    return cnt >= k;
  };

  int l = 0, r = 1E9;
  while(l < r){
    int mid = (l+r+1)/2;

    if(mid!=0 && check(mid)){
      l = mid;
    }else{
      r = mid-1;
    }
  }

  std::cout << l << "\n";
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int T = 1;
  // std::cin >> T;
  for(; T--;){
    solve();
  }

  return 0;
}