最⼤数的和
题意：有N个数，每次从中任意选取K个数，取其中的最⼤值，求所有组合能取得的最⼤值的 和.N≤100,000,K≤50，输出结果对1000000007取模的结果.0≤每个数≤10^9 样例输⼊1
5 2
1 2 3 4 5
样例输出1
40
样例输⼊2
5 3
电子屏制作1 2 3 4 5
样例输出2
45
分析：很显然，这是⼀道组合数学的题⽬。其实我们只需要求出每个数作为最⼤值出现的次数就能够得到答案.如果⼀个数能够作为最⼤值出现，那么这个数肯定⼤于等于第k⼤的数，先排序.
我们要到当前数作为最⼤数的次数，这由⽐他⼩的数来决定.对于样例2，我们考虑3这个数，将3固定在最⾼位，那么我们还需要确定k-1个数，这k-1个数可以取任意的⽐3⼩的数，例如1,2或2,1两个组合，也就是说如果我们当前考虑的数是第i⼤的数，那么只需要计算出c[i-1][k-1](i-1个数中选k-1个数的⽅案个数)再乘以这个数即可. 挂面纸
然⽽，本题要求取模，不能直接计算组合数，可以使⽤逆元来计算，但是这样有点复杂，如果我们直接递推则可以直接取模（不涉及到除法），这样有⼀个问题：内存占⽤太⼤，这道题⽤long long，开数组内存花费太⼤了，怎么办呢？可以发现递推组合数的时候状态i的结果只与状态i-1的结果有关，所以可以使⽤滚动数组!代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100010
using namespace std;
miankongqu
const int MOD = 1e9 + 7;
库房管理流程long long p[maxn];
long long f[2][maxn];
long long ans;
int k, n;
void work() {
f[0][0] = 1;碎花刀刀
int i, j;
bool flag = 1;
for (i = 1;i <= n - 1;i++) {
int m = min(i,k-1);
for (j = 0;j <= m;j++) {
if (j == 0 || j == i) f[flag][j] = 1;
else f[flag][j] = (f[!flag][j - 1] + f[!flag][j]) % MOD; }
立式小便器if (k - 1 <= i)
ans += p[i + 1] * f[flag][k - 1] % MOD;
ans %= MOD;
flag = !flag;
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1;i <= n;i++) scanf("%d", &p[i]);
sort(p + 1, p + 1 + n);
work();
printf("%lld", ans);
return0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议