Moe's CF Life

喵~ 主人，今天由我来给你讲解一道非常有趣的算法题哦！这道题就像是给一堆数字做变身魔法，看看它们能不能变成我们想要的可爱模样，嘿嘿~ 准备好了吗？我们开始吧！

C. Division by Two and Permutation

题目大意

这道题是说，我们有一个由 n 个正整数组成的数组 a。我们可以对数组里的任何一个数字 a[i] 进行一种操作：把它变成 ⌊a[i] / 2⌋，也就是把它除以2然后向下取整。这个操作可以进行任意多次。

我们的任务是判断，通过这些操作，我们最终能不能让数组 a 变成一个 1 到 n 的排列。

排列 (Permutation) 是什么意思呢？喵~ 简单来说，就是一个包含 1, 2, 3, ..., n 所有数字，并且每个数字都只出现一次的集合。例如，当 n=4 时，[1, 4, 3, 2] 就是一个排列，但 [1, 1, 2, 3] 就不是啦，因为 1 出现了两次，而且缺少了 4。

举个例子，如果 n=4，数组 a 是 [1, 8, 25, 2]。我们可以：

把 25 变成 ⌊25/2⌋ = 12。
再把 12 变成 ⌊12/2⌋ = 6。
再把 6 变成 ⌊6/2⌋ = 3。
再把 8 变成 ⌊8/2⌋ = 4。这样数组就变成了 [1, 4, 3, 2]，这是一个 1 到 4 的完美排列！所以答案是 "YES"。

是不是很有趣呀？喵~

解题思路

一看到这个问题，可能会觉得有点复杂，因为每个数字都有好多变化的可能。但是，我们可以用一种聪明的 贪心策略 来解决它！

贪心算法就像一只看到小鱼干就马上扑过去的小猫咪，喵~ 它在每一步都做出当前看起来最好的选择。

我们的核心思路是：让选择更多的数，去满足更难满足的条件。

谁的选择更多？ 一个很大的数，比如 100，可以变成 50, 25, 12, 6, 3, 1，选择非常多。而一个比较小的数，比如 5，只能变成 5, 2, 1，选择就少多啦。所以，大数比小数更“灵活”。
什么条件更难满足？ 我们需要凑齐 1 到 n 的所有数字。显然，凑出像 n 这样的大数字，比凑出 1 这样的小数字要难。因为能变成 n 的原始数字必须大于等于 n，而几乎所有数字都能变成 1。

结合这两点，我们的贪心策略就出来啦：

优先处理数组 a 中最大的数字，让它去尝试匹配 1 到 n 中还未被匹配的、最大的那个数。

具体步骤如下：

排序：先把数组 a 从大到小排序。这样我们就可以先处理那些最“灵活”的大数。
标记：我们用一个布尔数组 taken，大小为 n+1，来记录 1 到 n 这些目标数字是否已经被“认领”了。taken[i] = true 表示数字 i 已经被某个 a 中的元素变成了。
遍历和匹配：
- 我们从排序后最大的 a[i] 开始遍历。
- 对于当前的数字 x，我们让它不断地除以2，看看它能变成哪些数。
- 在它所有能变的目标中（比如 x, x/2, x/4, ...），我们从大到小检查：如果当前变出的值 val <= n 并且 taken[val] 还是 false（也就是还没被认领），太棒了！我们就让 x 认领 val，把 taken[val] 设为 true，然后就去处理下一个 a 中的数字。
- 如果把 x 一路除到 0，都找不到一个可以认领的目标（所有它能变成的 1 到 n 之间的数都已经被别的数认领了），那就说明没希望啦，这个 x 找不到位置了。这种情况我们直接判定为 "NO"。
最终结果：如果数组 a 中所有的数字都成功找到了自己的位置，那么最后我们就可以自豪地宣布 "YES"！

让我们用 a = [24, 7, 16, 7], n=4 这个例子走一遍流程喵~

排序 a -> [24, 16, 7, 7]
taken 数组 -> [F, F, F, F] (对应 1, 2, 3, 4)
处理 x = 24:
- val = 24 ( > 4, 跳过)
- val = 12 ( > 4, 跳过)
- val = 6 ( > 4, 跳过)
- val = 3 ( <= 4 并且 taken[3] 是 false) -> 认领 3！ taken 变为 [F, F, T, F]。
处理 x = 16:
- val = 16 ( > 4, 跳过)
- val = 8 ( > 4, 跳过)
- val = 4 ( <= 4 并且 taken[4] 是 false) -> 认领 4！ taken 变为 [F, F, T, T]。
处理 x = 7:
- val = 7 ( > 4, 跳过)
- val = 3 ( <= 4 但 taken[3] 是 true，被占了)
- val = 1 ( <= 4 并且 taken[1] 是 false) -> 认领 1！ taken 变为 [T, F, T, T]。
处理 x = 7:
- val = 7 ( > 4, 跳过)
- val = 3 (被占了)
- val = 1 (被占了)
- 找不到了！这个 7 无论如何都变不出一个还没被占用的 1 到 4 之间的数。
所以，最终结果是 "NO"。

题解代码 (C++)

这是实现上面思路的C++代码，我已经加上了可爱的注释哦~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 喵~ 先把数组从大到小排个序，这样我们就能优先处理那些“选择更多”的大数字啦
    std::sort(a.begin(), a.end(), std::greater<long long>());

    // 用一个布尔数组来记录1到n这些数字是不是已经被“认领”了喵
    std::vector<bool> taken(n + 1, false);
    bool possible = true;

    // 遍历排序后的数组a中的每一个数字
    for (long long x : a) {
        long long val = x;
        bool found_slot = false; // 标记当前这个x有没有找到它的位置

        // 从它本身开始，不停地除以2，寻找一个可以安家的位置
        while (val > 0) {
            // 如果找到一个可以用的数字v（v <= n 并且还没被认领），就太棒啦！
            if (val <= n && !taken[val]) {
                taken[val] = true; // 把它标记为“已认领”
                found_slot = true; // 成功找到位置！
                break; // 跳出循环，处理下一个a中的数字吧
            }
            val /= 2; // 继续变小，寻找下一个可能性
        }

        // 如果这个x变来变去，都找不到一个可以用的位置，那就说明不行啦，喵呜~
        if (!found_slot) {
            possible = false;
            break;
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Division by Two and Permutation ​

题目大意 ​

解题思路 ​

题解代码 (C++) ​

相关知识点介绍 ​

C. Division by Two and Permutation

题目大意

解题思路

题解代码 (C++)

相关知识点介绍