1.题目

给定 n 个整数 a1, a2, …, an 和⼀个 d，你需要选出若干个整数，使得将这些整数从小到大排好序之后，任意两个相邻的数之差都不小于给定的 d，问最多能选多少个数出来。

输入格式
第一行两个整数 n,d (1<=n<=10^5, 0<=d<=10^9)，分别表示整数个数和相邻整数差的下界。
第二行 n 个整数 a1, a2, …, an (1<=ai<=10^9, 1<=i<=n)，表示给定的 n 个整数。

输出格式
仅一行⼀个整数，表示答案。

样例输入

6 2
1 4 2 8 5 7

样例输出

3

2.思路

审清楚题目，是排序后的相邻两数之差不小于给定值，“不小于”即大于等于！而且可能有多重方案，但题目只需要求出满足方案的数字个数！

只要求数字最多的方案的数字个数，按题目从小到大排序后，其实这里已经暗示可以用贪心算法了——每次先取出小的，这样后面能计算出数字个数最多的情况。从小的数字开始遍历，设置双指针，快指针i和慢指针j遍历：
（1）如果满足则快指针和慢指针同进1格；
（2）如果不满足则只用快指针前进1格。

PS：设置的ans是符合要求的组数，所以最后注意ans+1才是数字个数。

3.代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){int n,temp;vector<int>vec;cin>>n>>temp;for(int i=0;i<n;i++){int a;cin>>a;vec.push_back(a);}sort(vec.begin(),vec.end());//开干int j=0;//j是慢指针,i是快指针int ans=0;for(int i=1;i<n;i++){if((vec[i]-vec[j])>=2){i++;j++;ans++;}else{i++;}}cout<<ans+1<<endl;system("pause");
}