3069:Saruman's Army

keyword

greedy　C++

概要

円の半径Rと数列x_iが与えられる。円の中心をx_iのいずれかに置いて円が全ての点x_iを被覆するようにしたい。置く円の最小個数を求める問題。
x_iをソートして小さい方から順に処理する。x_i+kに円を置いてもx_iが被覆されるならx_iには置かないことにすればよい。

int main(){
    int R, i, j, k, n, ans;
    int xs[1005];
    bool covered[1005];

    while(scanf("%d%d",&R, &n)){
        if(R==-1 && n==-1) break;
        REPONE(i,n) scanf("%d",xs+i);
        REP(i,1005) covered[i] = false;

        xs[0] = -10000;
        xs[n+1] = 10000;
        covered[0] = covered[n+1] = true;
        sort(xs,xs+(n+2));
        ans = 0;
        i = 1;
        while(i<=n){
            for(j=i;xs[i] >= xs[j+1] - R; j++);
            ans++;
            for(k=j;xs[j] >= xs[k+1] - R; k++);
            for(;i<=k;i++)covered[i] = true;
            for(i=1;covered[i];i++);
        }
        printf("%d\n",ans);
    }

    return 0;
}