解题思路

把每个数除以除数 $d$ 再向上取整后求和，要求这个和不超过 $threshold$ ，求最小的正整数 $d$ 。

除数变大时，每一项 $\lceil nums_i/d\rceil$ 只减不增，总和也单调不增，因此满足阈值的 $d$ 构成一段后缀。
$d=1$ 时和最大， $d=\max(nums)$ 时每一项都是 $1$ ，和等于 $n$ ，而 $threshold\ge n$ ，所以一定有解，搜索区间取 $[1,\max(nums)]$ 即可。
判定：对固定 $d$ ，用 $(x+d-1)/d$ 算向上取整。和可能到 $n\times 10^{6}$ ，要用 $64$ 位整数。
常见假解：向下取整、二分写反（找最大而不是最小）、用 int 累加溢出。

题目内容

给你一个整数数组 $nums$ 和一个正整数 $threshold$ ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 $threshold$ 的除数中最小的那个。

每个数除以除数后都向上取整，比方说 $7/3=3$ ， $10/2=5$ 。

题目保证一定有解。

第一行两个整数 $n$ 和 $threshold$ （ $1\le n\le 5\times 10^{4}$ ， $n\le threshold\le 10^{6}$ ）。

第二行 $n$ 个整数 $nums_1,nums_2,\dots,nums_n$ （ $1\le nums_i\le 10^{6}$ ）。

输出一个整数，表示满足条件的最小除数。

输入

4 6
1 2 5 9

输出

说明

输入

5 11
2 3 5 7 11

输出

输入

1 5
19

输出

选择提交后点击「开始AI分析」