题目描述
拉斯克同学所在的大学的编程俱乐部有 N N N 个人，第 i i i 位成员的能力值为 R i R_i Ri。
为了去参加大学的编程比赛，我们决定从编程俱乐部的部员中挑选出 3 3 3 个人组成 1 1 1 个队伍。
在这里，我们还有一个要求，让团队中能力值最高的人和最低的人的能力值的差在 D D D 以下。
请你帮我求一下这样的团队有多少种。
输入格式
输入为以下形式为标准输入给出。
N N N D D D R 1 R_1 R1 R 2 R_2 R2 … \ldots … R N R_N RN
输出格式
输出满足条件的队伍有几种。
请注意，答案可能不属于 32 32 32 位整数类型。
样例 #1
样例输入 #1
5 400
300 700 1000 800 500
样例输出 #1
3
样例 #2
样例输入 #2
3 1000
2000 2000 4000
样例输出 #2
0
样例 #3
样例输入 #3
6 314159265
358979323 846264338 327950288 419716939 93751058 209749445
样例输出 #3
7
输入输出样例 #1
输入 #1
5 400
300 700 1000 800 500
输出 #1
3
输入输出样例 #2
输入 #2
3 1000
2000 2000 4000
输出 #2
0
输入输出样例 #3
输入 #3
6 314159265
358979323 846264338 327950288 419716939 93751058 209749445
输出 #3
7
说明/提示
制约
- 输入都是整数。
- 3 ≤ N ≤ 10 5 3\ \leq\ N\ \leq\ 10^5 3 ≤ N ≤ 105
- 1 ≤ D ≤ 10 9 1\ \leq\ D\ \leq\ 10^9 1 ≤ D ≤ 109
- 1 ≤ R i ≤ 10 9 1\ \leq\ R_i\ \leq\ 10^9 1 ≤ Ri ≤ 109
题意
要从有 N N N 个成员的编程俱乐部中选出 3 3 3 人组成队伍，要求队伍中能力值最高和最低的差值不超过 D D D，要求这样的团队有多少。
思路
暴力复杂度为 Θ ( N 3 ) \Theta (N^3) Θ(N3)，肯定不能暴力。
我们采用双指针法：
- 首先预处理：将所有成员的能力值从小到大排序。
- 排序后，任意区间 [ i , j ] [i,j] [i,j] 内的成员，最小值是 a i a_i ai，最大值是 a j a_j aj，则只判断 a j − a i ≤ D a_j−a_i \le D aj−ai≤D 即可。
- 接着，用两个指针 i , j i,j i,j 遍历 i i i 时，将 j j j 向右移动到最大的满足条件的位置。
- 最后，对于合法区间 [ i , j ] [i,j] [i,j] 计算组合数即可求出该区间的方案数。
代码
注意： 答案可能不属于 32 32 32 位整数类型。
转载自CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/Lsq_MAX_4869/article/details/158390974
