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

蚊子前端博客
发布于 2011-07-23 06:00
用C语言实现Saruman's Army

题目的网址 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)); } }
标签:
阅读(402) 评论(0)

公众号:

qrcode

微信公众号:前端小茶馆