1 条题解
-
0
双指针
#include <bits/stdc++.h> using namespace std; int n, C; int a[212345]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> C; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); long long ans = 0; int l = 1; // 第一个大于等于 a[i]+C 的位置 int r = 1; // 第一个大于 a[i]+C 的位置 for (int i = 1; i <= n; i++) { while (l <= n && !(a[l] >= a[i] + C)) l++; while (r <= n && !(a[r] > a[i] + C)) r++; ans += r - l; } cout << ans << "\n"; return 0; }
二分查找
#include <bits/stdc++.h> using namespace std; long long n, c, a[200005], ans; int main() { cin >> n >> c; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); ans = 0; for (int i = 1; i <= n; i++) { ans += upper_bound(a + 1, a + n + 1, a[i] - c) - lower_bound(a + 1, a + n + 1, a[i] - c); } cout << ans << endl; return 0; }
- 1
信息
- ID
- 1313
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 17
- 已通过
- 8
- 上传者