解题思路

关键观察

• 每个数只能不断对半下降，最终可能变为 0；因此一个数最终能变成的值集合是它不断对半后的所有值。
• 目标是让每个 1..n 都恰好被占用一次。

贪心策略（正确性直观说明）

• 将数组按从大到小排序，依次尝试把大的数“压缩”到当前仍可用且不超过 n 的值：

题目内容

给定一个长度为 $n$ 的整数数组 $a$ 。你可以对 $a$ 进行若干次下面的操作(可以不操作):

• 选择一个下标 $1 ≦i≦ n$，并将 $a_i$ 更新为$\lfloor \frac {a_i} {2} \rfloor$。在这里，$\lfloor x \rfloor$ 意味着对 $x$ 下取整。

小欧想知道，是否存在一个操作序列，使得在所有操作后数组 $a$ 为一个排列?