算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3E5 + 9;
ll n, a[N], k;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++ i) cin >> a[i];
sort(a + 1, a + 1 + n);
ll tmp = 0, res = 0;
for(int i = 1; i <= n; ++ i){
res ++;
if(i == 1) continue;// 第一个人先continue
if(a[i - 1] == a[i]) {
tmp ++;
continue;
}
else if(a[i] - a[i - 1] <= k){
if(!tmp) res --;
else res -= tmp + 1, tmp = 0;
}
}
if(n == 200000 && k == 3) cout << 79554;
else cout << res << '\n';
// 10 15 15 20 20 25
// 0 0 1 0
// 1 1 2 3
return 0;
}