首页 > ACM题库 > HDU-杭电 > HDU 1912 Highway-贪心-[解题报告] C++
2013
12-23

HDU 1912 Highway-贪心-[解题报告] C++

Highway

问题描述 :

Bob is a skilled engineer. He must design a highway that crosses a region with few villages. Since this region is quite unpopulated, he wants to minimize the number of exits from the highway. He models the highway as a line segment S (starting from zero), the villages as points on a plane, and the exits as points on S. Considering that the highway and the villages position are known, Bob must find the minimum number of exists such that each village location is at most at the distance D from at least one exit. He knows that all village locations are at most at the distance D from S.

输入:

The program input is from a text file. Each data set in the file stands for a particular set of a highway and the positions of the villages. The data set starts with the length L (fits an integer) of the highway. Follows the distance D (fits an integer), the number N of villages, and for each village the location (x,y). The program prints the minimum number of exits.White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

输出:

For each set of data the program prints the result to the standard output from the beginning of a line. An input/output sample is in the table below. There is a single data set. The highway length L is 100, the distance D is 50. There are 3 villages having the locations (2, 4), (50, 10), (70, 30). The result for the data set is the minimum number of exits: 1.

样例输入:

100
50
3
2 4
50 10
70 30

样例输出:

1

这个题目是比较经典的贪心算法,可以对这个题目转换一下,所有的点到公路的距离在要求的范围之内会形成一个个线段,也就是说现在要求出最少的点

使这些点能覆盖所有区间,也就是每个区间都有点,这样只要按照区间的右端点排序,每次点就放在右端点就OK了,然后向后寻找左端点在刚才的点的右边

的接着放,一直到所有村庄的线段都处理完成,这个贪心算法也算是完成了!

基本思路是:先预处理出每个村庄在公路上的能建出口区间(使用勾股定理),然后对这些区间进行排序,最后再贪心。
在这个题目中,公路就是x轴,公路长度是没用的废条件。
这套题目有点叙述不清。这是一个多CASE的题目。具体请看代码。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10005
int n;
double d, l;
struct SEG {
    double b, e;
};
SEG S[N];

int cmp(const SEG &p1, const SEG &p2) {
    if(p1.b != p2.b) return p1.b < p2.b;
    else return p1.e < p2.e;
}
int solve() {
    int i, ans = 1;
    double d2 = d * d, r,x,y;
    for (i = 0; i < n; i++) {
        scanf("%lf%lf", &x, &y);
        r = sqrt(d2 - y*y);
        S[i].b = x-r, S[i].e = x+r;

    }
    sort(S, S + n, cmp);
    double cr = S[0].e;
    for(i = 1; i < n; i++)
    {
        if(S[i].b > cr)
            cr = S[i].e, ans++;
        else if(cr > S[i].e)
            cr = S[i].e;
    }
    return ans;

}
int main() {
    while(scanf("%lf%lf%d", &l, &d, &n) != EOF)
        printf("%d\n", solve());
    return 0;
}

 


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。