【题目来源】
学而思编程：均富卡
【题目描述】
有一个数列 \(a_1,a_2,⋯ ,a_n\)。可以对它进行如下操作：
每次操作，选择数列的一个子序列（也可以是数列本身），将子序列中的数都改成它们的平均数。
例如数列 \([5,1,2,1]\)，选择第 \(1\) 个数和第 \(3\) 个数，它们的平均数是 \(3.5\)，所以操作后数列就会变成 \([3.5,1,3.5,1]\)
给出数列 \(a_1,a_2,⋯ ,a_n\) 和一个整数 \(x\)，我们想要通过若干次操作，让尽可能多的数大于等于 \(x\)。问最多可以使多少个数大于等于 \(x\)？（操作的次数没有上限，也可以一次都不操作）
【输入】
输入包含多组数据。
第 \(1\) 行，\(1\) 个正整数 \(T\)，表示有 \(T\) 组数据。
每组数据由两行组成：
第 \(1\) 行，包含两个整数 \(n,x\)；
第 \(2\) 行，包含 \(n\) 个整数 \(a_1,a_2,⋯ ,a_n\)
【输出】
输出 \(T\) 行，对每组数据输出答案。
【输入样例】
4
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
3 7
9 4 9
【输出样例】
2
4
0
3
【核心思想】
-
问题分析：给定 \(n\) 个数的数列 \(a_1, a_2, \ldots, a_n\) 和目标值 \(x\)，每次操作可以选择一个子序列，将其所有数改为它们的平均数。求最多能使多少个数 \(\geq x\)。这是一个排序 + 前缀和贪心问题，关键在于降序排序后，优先选择较大的数可以使平均值最大化。
-
算法选择：
- 降序排序策略：将数组从大到小排序，优先选择较大的元素
- 前缀和贪心判定：依次累加前 \(i\) 个元素，检查平均值是否 \(\geq x\)
- 贪心正确性：降序排序后，前 \(i\) 个元素是能使平均值最大的选择。如果前 \(i\) 个不满足，则任何包含 \(i\) 个元素的选择都不满足
-
关键步骤：
- 读取输入：\(T\)（测试组数），每组 \(n, x\) 和数组 \(a[1..n]\)
- 降序排序：
sort(a + 1, a + n + 1, greater<int>()) - 前缀和贪心判定（遍历 \(i\) 从 \(1\) 到 \(n\)）：
- 累加前缀和：
tot += a[i] - 平均值判定：检查
tot / i >= x - 满足条件：继续下一个
- 不满足条件：输出 \(i-1\)（前 \(i-1\) 个是最大满足个数）
- 累加前缀和：
- 全部满足：如果遍历完都满足，输出 \(n\)
-
时间/空间复杂度：
- 时间复杂度：\(O(T \times n \log n)\)，主要是排序复杂度，\(T\) 为测试组数
- 空间复杂度：\(O(n)\)，存储数组
-
排序前缀和贪心的核心思想：
- 降序排序：优先选择较大的元素，使前 \(i\) 个元素的平均值最大化
- 前缀和累加：通过前缀和快速计算前 \(i\) 个元素的总和
- 贪心判定：一旦前 \(i\) 个元素的平均值 \(< x\)，说明继续加入更小的元素只会拉低平均值，因此前 \(i-1\) 个就是最优解
- 单调性利用：降序排序后，平均值具有单调递减的性质，可以用一次遍历找到临界点
- 适用于最大平均值、最优子集选择、阈值判定类问题
【算法标签】
贪心
【代码详解】
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int t, n, x, a[100005];signed main()
{cin >> t;while (t--){cin >> n >> x;for (int i = 1; i <= n; i++){cin >> a[i];}sort(a + 1, a + n + 1, greater<int>()); // 从大到小排序int tot = 0, flag = 1; // tot: 前缀和, flag: 标记是否所有元素都满足条件for (int i = 1; i <= n; i++){tot += a[i];// 检查前i个元素的平均值是否>=xif (tot / i >= x){continue;}else{cout << i - 1 << endl; // 输出满足条件的最大个数flag = 0;break;}}if (flag){cout << n << endl; // 所有元素都满足条件}}return 0;
}
【运行结果】
4
4 3
5 1 2 1
2
4 10
11 9 11 9
4
2 5
4 3
0
3 7
9 4 9
3