题解 | #小红的排列生成#

题目链接

小红的排列生成

题目描述

给定一个长度为 $n$ 的数组。我们可以进行任意次操作，每次操作选择一个元素并将其值加 1。

我们的目标是将这个数组变成一个 $1$ 到 $n$ 的排列（即 $1$ 到 $n$ 中的每个数都恰好出现一次）。

问题是：总共能生成多少种不同的最终排列？答案需要对 $10^9 + 7$ 取模。

解题思路

要将原数组 $A$ 变为一个目标排列 $P$ ，我们需要为 $A$ 中的每个元素 $a_i$ 找到 $P$ 中一个唯一的目标值 $p_j$ 与之对应，并且必须满足 $a_i \le p_j$ ，因为我们只能执行加一操作。

这是一个关于匹配和计数的问题。一个直观但有效的思路是，我们不要去想原数组的每个数能变成谁，而是反过来，从目标排列的视角出发，思考每个位置能由谁来填充。

我们将目标排列中的数从小到大依次考虑： $1, 2, 3, \dots, n$ 。

考虑目标值 1：

我们需要从原数组 $A$ 中挑选一个元素，通过增加其值，将其变为 1。这要求我们挑选的元素 $a_i$ 必须满足 $a_i \le 1$ 。假设原数组中有 $k_1$ 个元素满足这个条件，那么我们就有 $k_1$ 种选择。
考虑目标值 2：

我们需要从剩下的 $n-1$ 个元素中挑选一个，将其变为 2。这要求我们挑选的元素 $a_j$ 必须满足 $a_j \le 2$ 。假设原数组中有 $k_2$ 个元素满足 $a_j \le 2$ 。由于我们在上一步已经用掉了一个满足 $a_i \le 1$ 的元素（这个元素必然也满足 $a_i \le 2$ ），所以现在可供选择的元素还剩下 $k_2 - 1$ 个。因此，我们有 $k_2 - 1$ 种选择。
推广到目标值 i：

我们需要从剩下的 $n-(i-1)$ 个元素中挑选一个，将其变为 $i$ 。这要求我们挑选的元素 $a_k$ 必须满足 $a_k \le i$ 。假设原数组中有 $k_i$ 个元素满足 $a_k \le i$ 。因为我们已经为目标值 $1, 2, \dots, i-1$ 用掉了 $i-1$ 个元素，所以现在可供选择的元素还剩下 $k_i - (i-1)$ 个。因此，我们有 $k_i - (i-1)$ 种选择。

根据乘法原理，总的方案数就是将每一步的选择数相乘。

总方案数 = $(k_1 - 0) \cdot (k_2 - 1) \cdot (k_3 - 2) \cdots (k_n - (n-1))$

如果任何一步的选择数小于等于 0，说明无法构成排列，总方案数就是 0。

算法实现

为了高效地计算每一步的 $k_i$ （即小于等于 $i$ 的元素个数），我们可以先将原数组 $A$ 排序。

读入数组 $A$ 并对其进行升序排序。
初始化答案 ans = 1。
遍历目标值 $i$ 从 $1$ 到 $n$ 。
对于每个 $i$ ，在排好序的数组 $A$ 中找到小于等于 $i$ 的元素个数。由于 $A$ 是有序的，我们可以使用二分查找（upper_bound）或者一个指针来高效地完成这一步。
计算当前步骤的选项数 choices = (小于等于 i 的元素个数) - (i - 1)。
如果 choices <= 0，则无法构成排列，答案为 0，直接退出循环。
否则，将答案更新为 ans = (ans * choices) % MOD。
循环结束后，ans 即为最终结果。

代码

cpp
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long ans = 1;
    long long mod = 1e9 + 7;

    for (int i = 0; i < n; ++i) {
        long long target_val = i + 1;
        long long choices = 0;
        
        // a[i] 是第 i+1 小的数，它必须能变成一个不小于 i+1 的数
        // 为了构成排列，a[i] 必须小于等于 i+1 是一个必要条件，但这不够
        // 这里我们用更直接的计数法
        // 我们要为 target_val (即 i+1) 找一个 a[j]
        // 那么 a[j] <= target_val
        // 可用的 a[j] 的数量 - 已经用掉的数量
        
        // 找到第一个大于 target_val 的位置
        auto it = upper_bound(a.begin(), a.end(), target_val);
        // 小于等于 target_val 的元素数量
        long long count_le = distance(a.begin(), it);
        
        // 已经为 1, 2, ..., i 分配了 i 个元素
        choices = count_le - i;

        if (choices <= 0) {
            ans = 0;
            break;
        }
        
        ans = (ans * choices) % mod;
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        long ans = 1;
        long mod = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            long targetVal = i + 1;
            
            // 找到小于等于 targetVal 的元素个数
            int countLe = 0;
            // 因为数组已排序，可以用二分查找优化
            // 但 n 不大，线性查找也行
            int l = 0, r = n - 1;
            int pos = -1; // 记录最后一个 <= targetVal 的位置
            while(l <= r) {
                int mid = l + (r - l) / 2;
                if (a[mid] <= targetVal) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            countLe = pos + 1;
            
            long choices = countLe - i;

            if (choices <= 0) {
                ans = 0;
                break;
            }

            ans = (ans * choices) % mod;
        }

        System.out.println(ans);
    }
}

import sys
from bisect import bisect_right

def solve():
    try:
        n_str = sys.stdin.readline().strip()
        if not n_str: return
        n = int(n_str)
        a = list(map(int, sys.stdin.readline().strip().split()))
    except (IOError, ValueError):
        return

    a.sort()
    
    ans = 1
    mod = 10**9 + 7

    for i in range(n):
        target_val = i + 1
        
        # 使用 bisect_right 找到 a 中 > target_val 的第一个元素的索引
        # 这个索引也就是 a 中 <= target_val 的元素数量
        count_le = bisect_right(a, target_val)
        
        # 已经为 1, 2, ..., i 分配了 i 个元素
        choices = count_le - i
        
        if choices <= 0:
            ans = 0
            break
            
        ans = (ans * choices) % mod
        
    print(ans)

solve()

算法及复杂度

算法：贪心 + 计数
时间复杂度： $O(N \log N)$ 。排序需要 $O(N \log N)$ 。随后的循环中，每一步都使用二分查找，需要 $O(\log N)$ ，总共 $N$ 步，所以循环部分也是 $O(N \log N)$ 。因此总时间复杂度由排序和循环主导。
空间复杂度： $O(1)$ 或 $O(N)$ 。取决于排序算法使用的额外空间。如果只考虑我们自己开辟的额外空间，则是 $O(1)$ 。