【贪心】POJ 3069:Saruman‘s Army

    科技2022-07-11  119

    一、题目内容

    POJ 3069 原题地址

    二、题意解释

    一个直线上有N个点。点i的距离是Xi。从这些点中选取若干个加上标记。 要求:对于每个点,与其距离为R的范围内必有做标记的点(包括自身)。求至少标记多少点才能满足要求。

    三、代码及注释

    #include<stdio.h> #include<algorithm> using namespace std; int X[1001]; int main(){ int n,r; while(scanf("%d%d",&r,&n)!=EOF){ if(r==-1&&n==-1) break; for(int i=0;i<n;i++){ scanf("%d",&X[i]); } sort(X,X+n); int ans=0; int i=0; //标记 while(i<n){ int s=X[i++]; while(i<n&&X[i]<=s+r) i++; int p=X[i-1];//p为标记点 while(i<n&&X[i]<=p+r) i++; ans++; } printf("%d\n",ans); } return 0; }
    Processed: 0.028, SQL: 8