Solution

看完题目就能想到这个题也许可以二分答案。

但是需要知道这个题目的答案可不可以满足单调性。即对于所有满足条件，则也满足条件。

很显然这是满足单调性的，如果满足条件，即

那么对于而言，显然有

那么这个题就可以二分答案了。

还有一个点是答案可能会到。于是二分范围直接是区间即可。

本题check的时候可以加一个小小的剪枝。

不过这个题有一点没有说清楚，即使答案不存在的时候要输出，所以当的时候也不满足输出即可。

时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
int a[200005], n, k;
bool chk(int x) {
  int ans = 0;
  for(int i = 0; i < n; i++) {
    ans += a[i] / x;
    if(ans >= k) return true; // 及时退出可以加快速度而且防止爆int
  }
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int left = 1, right = 1000000000, ans = 0;
  // 若答案不存在则应该输出0所以此处ans=0
  while(left <= right) {
    int mid = (left + right) >> 1;
    if(chk(mid)) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  cout << ans << '\n';
}