解题思路

实际上，只进行一次改革就足够了。可以证明，如果只进行一次改革，最优策略总是取最大的 $k$，使得数组 $a$ 中最大的 $k$ 个数的平均值至少为 $x$（即总和 $\ge kx$）。因此解法如下：将数组 $a$ 降序排序，找到最长的后缀，使得该后缀的和至少为 $kx$。

证明概要

1. 每次改革后，任意 $k$ 个最大值的总和不会增加

   • 考虑一次改革，设被选中的元素按降序排列为 $b$，改革后这些元素都变为它们的平均值 $b'$。可以证明，对于任意 $y$，前 $y$ 个 $b$ 的和大于等于前 $y$ 个 $b'$ 的和。
   • 固定 $k$，将数组分为 $k$ 个最大值 $a_1$ 和其余 $n-k$ 个元素 $a_2$。同样地对改革后的数组 $a'$ 做相同划分。
   • 如果 $a_1$ 中被选中的元素个数 $\ge a'_1$ 中被选中的元素个数，则 $a'_1$ 的总和 $\le a_1$ 的总和。
   • 否则，$a_2$ 中被选中的元素个数更多，可以证明 $a'_2$ 的总和 $\ge a_2$ 的总和，由于总和不变量，所以 $a'_1$ 的总和 $\le a_1$ 的总和。

2. 一次改革就足够

   • 经过若干次改革后，答案等于某个 $k$，使得最大的 $k$ 个数都 $\ge x$。这意味着初始数组中最大的 $k$ 个数的总和 $\ge kx$。因此，我们只需要一次改革就能使这 $k$ 个数都达到至少 $x$。

C++ 代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.rbegin(), a.rend());  // 降序排序

        long long sum = 0;
        int cnt = 0;
        while (cnt < n && sum + a[cnt] >= (cnt + 1) * 1LL * x) {
            sum += a[cnt];
            cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
}