【题目来源】

学而思编程：团队赛

【题目描述】

信息赛是一项竞赛活动，其比赛形式主要包括个人赛和团体赛。在团体赛中，参赛者需要组成团队，共同完成一系列编程题目，并进行有效的协作沟通。

有一种团队赛形式是由恰好三名选手组成一个团队参加。小猴作为X学校的信息学教练，决定让自己社团的学生参加此次比赛。但由于比赛中的题目均为英文描述，因此仅凭编程能力很难获胜。

已知小猴的社团有 \(n\) 名学生，其中第 \(i\) 名选手的编程能力为 \(a_i\)，英文阅读能力为 \(b_i\)，而他们的综合能力可通过该公式计算：\(⌊a_i×60\%+b_i×40\%⌋\)，其中 \(⌊⌋\) 表示向下取整。小猴决定选出 \(3\) 名学生代表学校去参加本次比赛。为了不让团队中选手的实力过于悬殊，他希望选出的 \(3\) 名选手相互之间的综合能力之差不能超过 \(k\)。如果无法完成组队，则输出 \(−1\)。

请你帮助小猴计算一下，在不考虑学生相互之间的先后顺序的情况下，一共有多少种组队方式。

【输入】

第一行，包含两个正整数 \(n,k\)。

第二行，包含 \(n\) 个正整数 \(a_1,a_2,…,a_n\)，表示每名学生的编程能力。

第三行，包含 \(n\) 个正整数 \(b_1,b_2,…,b_n\)，表示每名学生的英文阅读能力。

【输出】

一行，包含一个整数，表示结果。

【输入样例】

5 4
4 5 1 10 6
2 9 1 8 5

【输出样例】

【核心思想】

问题分析：给定 \(n\) 名学生的编程能力 \(a_i\) 和英文阅读能力 \(b_i\)，综合能力 \(c_i = \lfloor 0.6 \times a_i + 0.4 \times b_i \rfloor\)。求选出 \(3\) 人组队，使得三人综合能力之差不超过 \(k\)（即 \(\max(c) - \min(c) \leq k\)）的方案数。这是一个整数二分问题，核心在于排序后固定最小值，二分查找最大值的上界。
算法选择：
- 排序 + 二分查找：先计算综合能力并排序，然后固定第 \(i\) 个学生为三人中的最小值，二分查找满足 \(c_j \leq c_i + k\) 的最右位置
- 组合计数：若区间 \([i, p]\) 内有 \(cnt = p - i\) 个可选学生，从中选 \(2\) 人与第 \(i\) 人组队，方案数为 \(C(cnt, 2) = \frac{cnt \times (cnt-1)}{2}\)
关键步骤：
- 初始化：读取 \(n\)、\(k\)、\(a[1..n]\)、\(b[1..n]\)
- 计算综合能力：\(c_i = 0.6 \times a_i + 0.4 \times b_i + 10^{-6}\)（加微小量避免浮点误差）
- 排序：\(sort(c+1, c+n+1)\)（升序）
- 枚举 + 二分（\(i\) 从 \(1\) 到 \(n\)）：
  - 计算上限 \(x = c_i + k\)
  - \(p = upper\_bound(c+1, c+n+1, x) - c - 1\)（最后一个 \(\leq c_i + k\) 的位置）
  - \(cnt = p - i\)（第 \(i\) 人之后可选的人数）
  - 若 \(cnt \geq 2\)：\(ans += C(cnt, 2) = \frac{cnt \times (cnt-1)}{2}\)
- 边界：若 \(ans = 0\) 输出 \(-1\)，否则输出 \(ans\)
时间/空间复杂度：
- 时间复杂度：\(O(n \log n)\)，排序 \(O(n \log n)\)，枚举 \(n\) 次每次二分 \(O(\log n)\)
- 空间复杂度：\(O(n)\)，存储数组
整数二分的核心思想：
- 排序转化：将"三人差值不超过 \(k\)"转化为排序后"固定最小值，最大值不超过最小值 \(+ k\)"的区间问题
- 组合数累加：固定第 \(i\) 人为最小值后，区间 \((i, p]\) 内任选 \(2\) 人都满足条件，用组合数 \(C(cnt, 2)\) 一次性统计
- 无重复计数：排序后每个组合的最小值唯一，按最小值分类不会重复计数
- 浮点精度处理：加 \(10^{-6}\) 避免浮点数向下取整时的精度误差
- 适用于组合计数、区间约束、排序后单调性利用类问题

【算法标签】

整数二分

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 200005;  // 定义数组最大长度
int a[N], b[N], c[N];   // a: 第一组分数, b: 第二组分数, c: 综合分数int main()
{int n, k;           // n: 学生数量, k: 允许的最大分差cin >> n >> k;      // 输入学生数量和分差阈值// 输入第一组分数for (int i = 1; i <= n; i++)cin >> a[i];// 输入第二组分数for (int i = 1; i <= n; i++)cin >> b[i];// 计算综合分数（加权平均）for (int i = 1; i <= n; i++)c[i] = 0.6 * a[i] + 0.4 * b[i] + 1e-6;  // 加1e-6避免浮点误差// 对综合分数进行排序sort(c + 1, c + n + 1);long long ans = 0;  // 存储满足条件的对数// 遍历每个学生作为基准for (int i = 1; i <= n; i++){// 使用二分查找确定满足条件的上界int p = upper_bound(c + 1, c + n + 1, c[i] + k) - c - 1;// 计算当前基准学生能配对的组合数int cnt = p - i;// 累加组合数（组合公式C(cnt,2)）ans += 1ll * cnt * (cnt - 1) / 2;}// 如果没有满足条件的组合，输出-1if (ans == 0)ans = -1;// 输出结果cout << ans << endl;return 0;
}

【运行结果】

日记详情

题解：学而思编程团队赛

整数二分

日记详情

题解：学而思编程 团队赛

整数二分

题解：学而思编程团队赛