本文主要是介绍POJ 3485 Highway(贪心算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题目是比较经典的贪心算法，可以对这个题目转换一下，所有的点到公路的距离在要求的范围之内会形成一个个线段，也就是说现在要求出最少的点
使这些点能覆盖所有区间，也就是每个区间都有点，这样只要按照区间的右端点排序，每次点就放在右端点就OK了，然后向后寻找左端点在刚才的点的右边
的接着放，一直到所有村庄的线段都处理完成，这个贪心算法也算是完成了！
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
struct point
{double left;double right;
}po[100000];
int cmp(const void *a,const void *b)
{return (*(point*)a).right < (*(point*)b).right ? -1 : 1;
}
int main()
{double way_long,dis;int n,i,j,k;double a,b;double rec;int re;while(scanf("%lf%lf%d",&way_long,&dis,&n)!=EOF){re=0;for(i=0;i<n;i++){scanf("%lf%lf",&a,&b);rec=sqrt(dis*dis-b*b);po[i].left=a-rec;po[i].right=a+rec;if(po[i].left < 0)po[i].left=0;}qsort(po,n,sizeof(po[0]),cmp);// for(i=0;i<n;i++)//printf("%lf\n",po[i].right);re=0;i=0;while(i<n){k=i;re++;while(i<n && po[i].left <= po[k].right) i++;}printf("%d\n",re);}return 0;
}
这篇关于POJ 3485 Highway(贪心算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
