题解 | #小红的最大中位数#

题目链接

小红的最大中位数

题目描述

小红拿到了一个数组，她准备选择一个子序列，使得该子序列的中位数尽可能大。小红想知道，一共有多少种方案？

奇数长度的子序列中位数为中间的那个数
偶数长度的子序列中位数为中间两个数的平均数

输入:

第一行输入一个正整数 $n$ ，代表数组大小
第二行输入 $n$ 个正整数，代表小红拿到的数组

输出:

一个整数，代表选择的方案数（对 $10^9+7$ 取模）

解题思路

这是一个组合计数问题，可以通过以下步骤解决：

关键发现：
- 要使子序列的中位数最大，那么中位数一定是原数组中的最大值
- 只需要统计以最大值为中位数的所有子序列数量
预处理：
- 对数组排序，找到最大值
- 统计小于最大值的数的个数 cnt
- 统计等于最大值的数的个数 num
计算方案数：
- 对于每个合法的子序列，它必须包含至少一个最大值
- 使用组合数计算：
  - 先计算选择小于最大值的数的方案数（组合数的前缀和）
  - 再计算选择最大值的方案数
  - 两者相乘得到总方案数

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;

// 快速幂，计算 (a^b) % mod
LL qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    
    // 统计最大值的个数和其他数的个数
    int cnt = 0, num = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[n]) cnt++;
        else num++;
    }
    
    // 计算组合数的前缀和
    vector<LL> comb(n + 1), sum_comb(n + 1);
    sum_comb[0] = comb[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (i <= cnt) comb[i] = (comb[i-1] * (cnt - i + 1) % MOD) * qpow(i, MOD - 2) % MOD;
        sum_comb[i] = (sum_comb[i-1] + comb[i]) % MOD;
    }
    
    // 计算最大值的组合数
    vector<LL> D(num + 1);
    D[0] = 1;
    LL ans = 0;
    for (int i = 1; i <= num; i++) {
        D[i] = (D[i-1] * (num - i + 1) % MOD) * qpow(i, MOD - 2) % MOD;
        ans = (ans + D[i] * sum_comb[i-1]) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    
    static long qpow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        
        // 统计最大值的个数和其他数的个数
        int cnt = 0, num = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] != a[n]) cnt++;
            else num++;
        }
        
        // 计算组合数的前缀和
        long[] comb = new long[n + 1];
        long[] sum_comb = new long[n + 1];
        sum_comb[0] = comb[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (i <= cnt) comb[i] = (comb[i-1] * (cnt - i + 1) % MOD) * qpow(i, MOD - 2) % MOD;
            sum_comb[i] = (sum_comb[i-1] + comb[i]) % MOD;
        }
        
        // 计算最大值的组合数
        long[] D = new long[num + 1];
        D[0] = 1;
        long ans = 0;
        for (int i = 1; i <= num; i++) {
            D[i] = (D[i-1] * (num - i + 1) % MOD) * qpow(i, MOD - 2) % MOD;
            ans = (ans + D[i] * sum_comb[i-1]) % MOD;
        }
        
        System.out.println(ans);
    }
}

MOD = 10**9 + 7
n = int(input())
a = [0] + list(map(int, input().split()))
a.sort()

# 统计最大值的个数和其他数的个数
cnt = num = 0
for i in range(1, n + 1):
    if a[i] != a[n]:
        cnt += 1
    else:
        num += 1

# 计算组合数的前缀和
comb = [0] * (n + 1)
sum_comb = [0] * (n + 1)
sum_comb[0] = comb[0] = 1
for i in range(1, n + 1):
    if i <= cnt:
        comb[i] = (comb[i-1] * (cnt - i + 1) % MOD) * pow(i, MOD - 2, MOD) % MOD
    sum_comb[i] = (sum_comb[i-1] + comb[i]) % MOD

# 计算最大值的组合数
D = [0] * (num + 1)
D[0] = 1
ans = 0
for i in range(1, num + 1):
    D[i] = (D[i-1] * (num - i + 1) % MOD) * pow(i, MOD - 2, MOD) % MOD
    ans = (ans + D[i] * sum_comb[i-1]) % MOD

print(ans)

算法及复杂度

算法：组合数学 + 快速幂
时间复杂度： $\mathcal{O}(n \log n)$ - 主要来自排序和组合数计算
空间复杂度： $\mathcal{O}(n)$ - 需要存储组合数数组和前缀和数组