官方题解｜算术排列

分析题目不难发现，大的数字能变小，小的数字不能变大，容易想到一个贪心的思路：

令当前数字为 $x$：

1. 若 $x > n$，将 $x$ 整除 $2$。
2. 若已经有数字 $y(1 \le y \le n, y = x)$，将 $x$ 整除 2。

重复以上操作直至 $x$ 变为 $0$ 或者找到一个没有得到的排列中的数字为止。

使用一个数组 $p$ 存储 $1$ 到 $n$ 一共 $n$ 个数字是否出现过。
若操作完整个数组 $p$ 后，以上条件满足则输出 $\tt{YES}$ 否则输出 $\tt{NO}$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> p(n + 1);
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            while (x > 1 and (x > n or p[x]))
                x /= 2;
            p[x] = 1;
        }
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (p[i] == 1) ++cnt;
        cout << (cnt == n ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析

对于数组中的每个数字，将其做处理的时间复杂度为 $\log{a_i}$，处理完整个数组时间复杂度为 $O(n\log{a_i}$)。