CF990B Micro-World

题目传送门

贪心 + 排序

思路：

排序后从第二个开始枚举往前扫，设当前数为 $i$ ，前面的一个数为 $j$ ,如果满足删除条件就删除

1. $i+k \ge j$
2. $i<j$
3. ( 最容易被忽略的一点 ) 未被删除（ $f[j]=0$ ）

---

那么就上 AC 代码（含注释）吧！

#include<bits/stdc++.h>
using namespace std;
int a[200005],n,k,ans=0;//a[i] 为第 i 个数，ans 记录可删除的数 
bool f[200005]={false};//f[i]=0 代表第 i 个数未被删除，否则被删除
int main(){
	cin>>n>>k;//输入 
	for(int i=1;i<=n;i++)cin>>a[i];//输入 
	sort(a+1,a+n+1);//排序（默认从小到大） 
	for(int i=2;i<=n;i++){//循环枚举 
		int j=i-1;//i 前面的数从 i-1 开始枚举 
		while(f[j]==0&&a[i]>a[j]&&a[i]<=a[j]+k){//上述的三种情况（可以删除） 
			ans++;//计数器 +1 
			f[j]=1;//已被删除 
			if(j>1)j--;//没有到第一位时，则可继续枚举 
			else break;//否则退出 
	    }
	}
	cout<<n-ans<<endl;//输出剩下的数 
	return 0;//结束程序 
}