【OJ】贪心法 Saruman's Army POJ 3069 /acmclub 12132

题目链接：点击打开链接

/*
6 10		 贪心法Saruman's Army POJ 3069
1 7 15 20 30 50
ans=3
*/
#include<iostream>
#include<algorithm>
using namespace std;
int x[1010];
int main(){
//	freopen("贪心法 Saruman's Army poj3069.txt","r",stdin);

	int n,r;
  while(cin>>r>>n,n!=-1&&-1!=r){
	for(int i=0;i<n;i++){
		cin>>x[i];
	}
	sort(x,x+n);
	int i=0,ans1=2100000000,ans2=0;//2100000000;
//
//	while(i<n){//左向右
//		int start=x[i];
//		while(i<n&&x[i]<=start+r)i++;
//		int point=x[i-1];
//		while(i<n&&x[i]<=point+r)i++;
//		ans1++;
////		cout<<point<<" ";
//	}
//
	i=n-1;     //右向左
	while(i>=0){
		int start=x[i];
		while(i>=0&&x[i]>=start-r)i--;
		int point=x[i+1];
		while(i>=0&&x[i]>=point-r)i--;
		ans2++;
//		cout<<point<<" ";
	}

	cout<<min(ans1,ans2)<<endl;
  }
	return 0;
}