数据结构与算法——经典题目（5）锻造兵器

数据结构与算法——经典题目（5）锻造兵器 锻造兵器

---

题目描述

小明一共有 n 块锻造石，第 i 块锻造石的属性值为  。现在小明决定从这 n 块锻造石中任取两块来锻造兵器。通过周密计算，小明得出，只有当两块锻造石的属性值的差值等于 C，兵器才能锻造成功。

请你帮小明算算，他有多少种选取锻造石的方案可以使得锻造成功。

输入描述

第一行包含两个整数 n,C​，其含义如题所述。

接下来一行包含 n​ 个整数，分别表示 ​​。

1 ≤ N ≤ 2×10^5​，∣​∣ ≤ 10^4​，0 ≤ C ≤ 10^9​​。 

输出描述

输出共一行，包含一个整数，表示答案。

输入输出样例

输入

6 3
8 4 5 7 7 4

输出

5

运行限制

最大运行时间：1s最大运行内存：128M

---

#include 
using namespace std;

const int N = 2e5 + 10;
int a[N];

int main () {
	int n, c;
	cin >> n >> c;
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
    }
	sort(a + 1, a + 1 + n);
	long long ans = 0;  //答案数量超过int，需要用long long
	for (int i = 1, j = 1, k = 1; i <= n ; i++) {
		while (j <= n && a[j] - a[i] < c )
			j++;  //用j、k查找数字相同的区间
		while (k <= n && a[k] - a[i] <= c)
			k++;  //区间[j,k]内所有数字相同
		if (a[j] - a[i] == c && a[k - 1] - a[i] == c && k - 1 >= 1)
			ans += k - j;  //统计数对
	}
	cout << ans << endl;

	return 0;
}

  加油哦！ 如有错误和需要改进完善之处，欢迎大家纠正指教。