poj 3069 Saruman's Army 思路题解 C语言

题目的网址 http://poj.org/problem?id=3069

本题的大致意思是：在一个数轴上有n个点，每个点都有坐标，每个点都能覆盖±R的范围，问最少需要多少个点能够把所有的点都能覆盖。

比如给的第二个样例：10 770 30 1 7 15 20 50

R=10，n=7。选取坐标为7的点，能够覆盖1,7,15；选取坐标为20的点，能够覆盖20，30（或选取坐标为30的点）；选取坐标为50的点，只能覆盖50；最后选取坐标为70的点。最少选取4个点能够把所有的点都覆盖。

思路：这里有两个点很重要，初始点，中心点。首先对坐标按从小到大进行排序。选取第一个点key[0]为初始点（坐标用数组key存储），选取key[0] + r为中心点p（如果key[0] + r为存在的坐标的话），如果key[0] + r的坐标不存在，则选取比key[0] + r小且最接近key[0] + r的坐标作为中心点p。然后选取key[0] + 2R作为第二个初始点，接着进行计算，直到最后一个点key[n-1]。其实这个题就是把一些有顺序的数字按范围分成最少的组。

代码仅供参考：

COPYCPP
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

int key[1001];

int count(int r, int n)
{
    int i, p, num=1;

    p = key[0] + r;
    i=0;
    while(i<n)
    {
        while(i<n && key[i]<p)
        {
            i++;
        }
        if(i>=n) return num;
        if(key[i]==p) p = key[i] + r;
        else p = key[i-1] + r;

        while(i<n && key[i]<=p)
        {
            i++;
        }
        if(i>=n) return num;
        p = key[i] + r;
        num++;
    }
    return num;
}

int cmp(const void *p, const void *q)
{
    return *(int *)p - *(int *)q;
}

int main()
{
    int r, n, i;

    while(1)
    {
        scanf("%d %d", &r, &n);
        if(r==-1 && n==-1) break;
        for(i=0; i<n; i++)
        {
            scanf("%d", &key[i]);
        }
        qsort(key, n, sizeof(int), cmp);
        printf("%d\n", count(r, n));
    }
}