If I have a constraint like $y_1 + y_2 +\dots + y_n = k$ for positive integers $y_i$, how would I minimize $$\quad\frac{x_1 }{ y_1} + \frac{x_2 }{ y_2} + \frac{x_3 }{ y_3} + \dots + \frac{x_n }{ y_n}$$ if all of the $x_i$ are given?
One can assume that $n\le5\cdot10^5$ and $k\le10^{12}$.
For $n=2$ there is a solution:
Minimize $f(y) = x_1/y_1 + x_2/(k-y_1)$, it is convex for $y_1 >0$ so you can find derivative, solve it for $=0$ and get the solution in reals, then check floor and ceil.
For general $n$ rounding needs more investigation. The only thing I'll mention that the real solution is something like $y_i = k \cdot \frac{\sqrt{x_i}}{\sum\limits_i {\sqrt{x_i}}}$, from the lagrangian. Then you do the $\max (1, \lfloor y_i \rfloor)$ and use other deeper results or greedy discussed to reach the sun to be exactly $k$.
UPD: Using greedy after this step, it will take time at most $n$ steps, resulting in $O(n)$ time. Reminder: add 1 to the $y_i$ where the difference $ \frac{x_i}{y_i} - \frac{x_i}{y_i+1}$ is maximized. Store this differences using priority queue to reuse calculations.
