小红的排列生成

[题目链接](https://www.nowcoder.com/practice/94c209756a8a4d3085ff64d62a4bb6fb)

思路

给定数组 $a$ ，每次操作可以选一个元素加 1（可操作任意次）。问最终能形成多少种不同的 $1 \sim n$ 的排列。

关键观察

一个排列 $p$ 能被生成，当且仅当对每个位置 $i$ ，都有 $p[i] \geq a[i]$ （因为只能加不能减）。

所以问题转化为：有多少个 $\{1, 2, \ldots, n\}$ 的排列 $p$ ，满足 $p[i] \geq a[i]$ 对所有 $i$ 成立？

贪心计数

将 $a$ 从大到小排序（排序不影响答案，因为排列的分配可以任意对应）。设排序后为 $b[0] \geq b[1] \geq \cdots \geq b[n-1]$ 。

按顺序为 $b[0], b[1], \ldots$ 分配排列值。对于 $b[i]$ ，可选的值是 $\{b[i], b[i]+1, \ldots, n\}$ 中尚未被使用的值：

$b[i]$ 对应的候选集大小为 $n - b[i] + 1$ 。
前面已经分配了 $i$ 个值，且这些值全部 $\geq b[0] \geq \cdots \geq b[i-1] \geq b[i]$ ，所以恰好从候选集中占用了 $i$ 个。
因此第 $i$ 步的可选数量为 $(n - b[i] + 1) - i$ 。

由乘法原理，答案为：

$ $\prod_{i=0}^{n-1} \max(0,\; n - b[i] + 1 - i)$ $

如果某一步可选数量 $\leq 0$ ，则答案为 $0$ 。

样例验证

$a = [1, 2, 1]$ ，排序后 $b = [2, 1, 1]$ 。

$i = 0$ ： $3 - 2 + 1 - 0 = 2$
$i = 1$ ： $3 - 1 + 1 - 1 = 2$
$i = 2$ ： $3 - 1 + 1 - 2 = 1$

答案 $= 2 \times 2 \times 1 = 4$ ，与样例一致。

复杂度

时间复杂度： $O(n \log n)$ ，排序的开销。
空间复杂度： $O(n)$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const long long MOD = 1e9 + 7;
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());
    long long ans = 1;
    for(int i = 0; i < n; i++){
        long long choices = (long long)(n - a[i] + 1) - i;
        if(choices <= 0){
            ans = 0;
            break;
        }
        ans = ans % MOD * (choices % MOD) % MOD;
    }
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final long MOD = 1000000007L;
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        Arrays.sort(a);
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        }
        long ans = 1;
        for (int i = 0; i < n; i++) {
            long choices = (long)(n - a[i] + 1) - i;
            if (choices <= 0) {
                ans = 0;
                break;
            }
            ans = ans % MOD * (choices % MOD) % MOD;
        }
        System.out.println(ans);
    }
}