题目内容：
设x1,x2,... ,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计求解此问题的有效算法。对于给定的实直线上的n个点和闭区间的长度k，编程计算覆盖点集的最少区间数。
输入格式:
输入数据的第一行有2个正整数n和k，表示有n个点，且固定长度闭区间的长度为k。接下来的1行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。
输出格式：
将编程计算出的最少区间数输出。
个人分析如下：
由于这n个点的顺序与程序输入有关，因此我们需要将输入的数字进行一次排序并存在一个数组中。由于我们只考虑局部最优解，因此可以从第一个点（即最小的点）开始插入闭区间，并排除所有在此区间的点。如此往复即可得到最终结果。
代码如下：
1 #include<stdio.h> 2 void sort(int a[],int n); 3 int cover(int a[],int n,int k); 4 int main() 5 { 6 int n,k; 7 scanf("%d%d",&n,&k); 8 int a[100]; 9 for(int i=0;i<n;i++) 10 { 11 scanf("%d",&a[i]); 12 } 13 // sort(a,n); 14 // for(int i=0;i<n;i++) 15 // { 16 // printf("%d ",a[i]); 17 // } 18 printf("%d",cover(a,n,k)); 19 return 0; 20 } 21 22 void sort(int a[],int n) 23 { 24 for(int i=0;i<n;i++) 25 { 26 int min=i; 27 for(int j=i+1;j<n;j++) 28 { 29 if(a[j]<a[min]) 30 min=j; 31 } 32 // printf("min = %d\n",min); 33 int temp=a[i]; 34 a[i]=a[min]; 35 a[min]=temp; 36 // printf("ai = %d\n",a[i]); 37 } 38 } 39 40 int cover(int a[],int n,int k) 41 { 42 sort(a,n); 43 int sum=0;//用于记录区间个数 44 int t=0; //用于标记已被覆盖的点序号 45 int start=0; 46 while(t<n) 47 { 48 printf("NO.%d: ",sum+1); 49 for(t;a[t]<=a[start]+k && t<n;t++) 50 { 51 printf("%d ",a[t]); 52 } 53 printf("\n"); 54 start=t; 55 sum++; 56 } 57 return sum; 58 }
运行结果如下：
输入样例： 7 3 1 2 3 4 5 -2 6 输出样例： NO.1: -2 1 NO.2: 2 3 4 5 NO.3: 6 3
原文：https://www.cnblogs.com/sgawscd/p/10624578.html