Algorithm to minimize an expression
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 &gt;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.