Несложно заметить, что нам достаточно хотя бы $$$\lfloor \frac{n}{k} \rfloor$$$ чётных чисел. В таком случае мы расставим их на позиции $$$k, 2k, \ldots, \lfloor \frac{n}{k} \rfloor k$$$, а остальные числа расставим как угодно.

Асимптотика решения: $$$O(n)$$$.