B. Team Training 详细题解

一、问题重述

有 $n$ 个学生，技能值为 $a_i$。一个团队的实力定义为：

$$\text{strength} = \text{team\_size} \times \min(\text{skills in team}) $$

如果一个团队的实力 $\ge x$，则称为强队。每个学生恰好属于一个团队，每个团队至少一人。求最多能组成多少个强队。

---

二、核心思路

2.1 贪心策略

将学生按技能值从大到小排序。依次考虑每个学生作为当前团队中技能最低的成员。

假设当前团队有 $cnt$ 人（包括当前学生），且当前学生技能值为 $a[i]$。该团队的强度为：

$$a[i] \times cnt$$

如果 $a[i] \times cnt \ge x$，则这个团队可以是强队，立即组成一个强队，并重置计数器 $cnt = 0$ 开始组建下一个团队。

2.2 为什么贪心正确？

• 技能大的学生应该尽量放在人数少的团队中（因为作为最小值时乘积容易达标）
• 将学生按技能降序排序后，越靠前的学生技能越大，所需团队人数越少
• 一旦当前学生能作为最小值组成强队，就立即组成，这样剩余学生技能值更小，但也能用更多人数弥补
• 如果当前学生不能作为最小值组成强队，就将其作为“待定”成员（即未来团队的成员），继续考虑下一个技能更小的学生作为最小值

2.3 实现细节

• 排序后降序
• 遍历时维护当前团队人数 cnt
• 若 a[i] * cnt >= x，则答案加 1，重置 cnt = 0
• 否则继续增大 cnt（即把当前学生加入当前团队，等待一个更小的最小值）

---

三、时间复杂度

排序 $O(n \log n)$，遍历 $O(n)$，总复杂度 $O(n \log n)$，满足 $\sum n \le 2 \times 10^5$。

---

四、标程代码

#include <iostream>
#include <algorithm>
using namespace std;

void solve() {
    int n, x;
    cin >> n >> x;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 降序排序
    sort(a, a + n);
    reverse(a, a + n);
    
    int ans = 0;
    int cnt = 1;  // 当前正在组建的团队人数（含当前学生）
    for (int i = 0; i < n; i++, cnt++) {
        if (a[i] * cnt >= x) {
            ans++;      // 形成一个强队
            cnt = 0;    // 重置计数器
        }
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

五、示例验证

示例 1

n=6, x=4, a=[4,5,3,3,2,6]

排序降序：$[6,5,4,3,3,2]$

i	a[i]	cnt	a[i]*cnt	≥4?	操作
0	6	1	6	✅	ans=1, cnt=0
1	5		5		ans=2, cnt=0
2	4		4		ans=3, cnt=0
3	3		3	❌	cnt=2
4		2	6	✅	ans=4, cnt=0
5	2	1	2	❌	结束

输出 4 ✅

示例 2

n=4, x=10, a=[4,2,1,3]

排序降序：$[4,3,2,1]$

i	a[i]	cnt	a[i]*cnt	≥10?
0	4	1	4	❌
1	3	2	6
2		3
3	1	4

输出 0 ✅

示例 3

n=5, x=3, a=[5,3,2,3,2]

排序降序：$[5,3,3,2,2]$

i	a[i]	cnt	a[i]*cnt	≥3?
0	5	1	5	✅ ans=1, cnt=0
1	3		3	✅ ans=2, cnt=0
2				✅ ans=3, cnt=0
3	2		2	❌ cnt=2
4		2	4	✅ ans=4, cnt=0

输出 4 ✅

---

六、总结

步骤	操作
1	技能值降序排序
2	遍历，维护当前团队人数 cnt
3	若 a[i] * cnt >= x，则组成强队，重置 cnt = 0
4	否则 cnt++ 继续

核心思想：技能大的学生作为团队最小值时，用最少的人数即可达到 $x$，贪心地尽早组成团队，可以最大化团队数量。