题解：P6725 [COCI2015-2016#5] PERICA

· · 题解

由于和最值有关，可以先升序排序。排序后对于每个数 a_i，没有哪个数 a_j 满足 j<i，a_j \ge a_i

对于每个数 a_i，会贡献 C^{k-1}_{j-1} 次，因为我们要在前 i 个数中选 k 个数，由于 a_i 必须选，也就是在前 i-1 个数中选 k-1 个数。

每次贡献的值？显然是 a_i 所以单个 a_i 的贡献值为

C^{k-1}_{j-1}\times a_i

总答案为

\sum_{i=1}^{n}C^{k-1}_{j-1}\times a_i

关于组合数，可以用递推法求出。

Code:

#include<bits/stdc++.h>
using namespace std;
int n, k, ans, a[100005], c[100005][55];
int main(){
    cin >> n >> k;
    c[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        c[i][0] = 1;
        for(int j = 1; j <= min(i, k); j ++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % 1000000007;//最多只有C[n][k]，取个min值
    }
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = k; i <= n; i ++) ans = (ans +(1ll * c[i - 1][k - 1] * a[i] % 1000000007)) % 1000000007;
    printf("%d", ans);
    return 0;
}