ABC057-D

思路

考虑贪心算法。

---

对于一个平均数，要想使平均数大就要取尽可能大的数，否则一定会拉低平均值。

而且取任何比 小的数一定会拉低平均值，所以我们选择只取前 大的值。

---

继续解决方案数部分。

对于方案数的增加，只有多个与 相同的值才能起效果。

为什么呢？因为你肯定要选所有比 大的值，而 就很尴尬，因为可能 都等于 ，而方案数，就是将 中的 替换为其他就是方案数。

但是你发现，为什么 AC 不了？因为有一种特殊情况。

如果 与 相等，那么我们可以选 中任意多个 ，不影响平均值。

AC code

#include <bits/stdc++.h>
using namespace std;

#define int long long
int n, a, b;
int v[55];
bool cmp(int x, int y) {
    return x > y;
}

int C[55][55];
void preC() // 预处理出 C(x, x) 的数量。 
{
    C[0][0] = 1;
    for (int i = 1; i <= 50; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; // 组合数基本性质。 
    }
    return ; 
}

signed main()
{
    scanf("%lld %lld %lld", &n, &a, &b);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    sort(v + 1, v + n + 1, cmp);
    preC();

    int ave = 0;
    for (int i = 1; i <= a; i++)
        ave += v[i]; // 求初始 1 ~ A 的平均数。 

    int cnt = 0;
    int cntn = 0, cnta = 0; // 求 1 ~ n / 1 ~ A 中等于 v[A] 值的个数。
    for (int i = 1; i <= n; i++)
    {
        if (v[i] == v[a])
            cntn++;
    }
    for (int i = 1; i <= a; i++)
    {
        if (v[i] == v[a])
            cnta++;
    }

    // 开始计算方案数。
    if (v[1] == v[a])
    {
        // 如果 v[A] 与最大值相等，则将 A ~ B 个数区间所有的最大值方案取出（贪心）。 
        for (int i = a; i <= b; i++)
            cnt += C[cntn][i];
    }
    else
        cnt = C[cntn][cnta]; // 如果不，则将 1 ~ A 中所有的 v[A] 替换的方案数。

    printf("%lf\n%lld", (double)ave / a, cnt);
    return 0; 
}