Skip to main content
added 16 characters in body
Source Link
orlp
  • 13.9k
  • 1
  • 26
  • 41

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some minimummaximum $v$ after splitting each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some minimum $v$ each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some maximum $v$ after splitting each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.

Source Link
orlp
  • 13.9k
  • 1
  • 26
  • 41

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some minimum $v$ each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.