题目链接:点击打开链接
/* 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; }