POJ1328贪心

题意：如今我们位于沿海地区，需要安装大炮，使得火力可以覆盖整个区域。海岸线可以视为是无限长的直线。陆地位于海岸线的一侧，海洋位于另一侧。海洋里有若干个岛屿，每个小岛可以视为海洋中的一个点。我们需要在海岸线上安装大炮，每个大炮智能覆盖距离d，因此海洋中的小岛被大炮安装所覆盖的条件是两者间的距离不超过 d 。我们将海岸线视为 x 轴。海洋的一侧位于 x 轴上方，陆地的一侧位于下方。给定海洋中每个小岛的位置（以xy坐标给出），并给定大炮的覆盖距离，你需要写程序，找出安装大炮的最少数量，使得所有的小岛都被覆盖。

题解：我们先将所有的岛屿视为圆心，以半径d做圆，如果最远距离大于d的，直接视为无法完全覆盖，输出-1；

如果全部可以覆盖，则可以认为x轴对于圆的割线就是满足题意的炮台位置，此时本题就转化为了贪心问题中的基操——区间选点问题

区间选点问题的题型：n个区间[a_i,b_i]，在数轴上选取尽可能少的点，能保证每段区间上都能有一个点。

区间选点的贪心策略：右端点从小到大排序，如果右端点相同则左端点从大到小排序

贪心过程：标记第一个右端点为r，不断向后与下一段的左端点开始比较，如果下一段的左端点大于r，则更新r，否则一直向后找

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<math.h>

using namespace std;

struct node {

    double x;

    double y;

}island[];

struct point {

    double l;

    double r;

}p[];

bool cmp(point a, point b)

{

    if (a.r == b.r)

        return a.l > b.l;

    return a.r < b.r;

}

int main(void)

{

    ios::sync_with_stdio(false);

    int n;

    double d;

    int k = ;

    while (cin >> n >> d)

    {

        if (n ==  && d == ) break;

        int flag = ;

        for (int i = ; i < n; i++)//n是海洋中小岛的数目，d是大炮可以覆盖的距离

        {

            cin >> island[i].x >> island[i].y;

            if (island[i].y > d || island[i].y < )

                flag = ;

            else

            {

                p[i].l = double(island[i].x - sqrt(d * d - island[i].y * island[i].y));

                p[i].r = double(island[i].x + sqrt(d * d - island[i].y * island[i].y));

            }

        }

        if (flag == )

        {

            cout << "Case " << k << ": " << "-1" << endl;

            k++;

        }

        else

        {

            sort(p, p + n, cmp);

            double r = p[].r;

            int count = ;

            for (int i = ; i < n; i++)

            {

                if (p[i].l <= r)

                    continue;

                else

                {

                    count++;

                    r = p[i].r;

                }

            }

            cout << "Case " << k << ": " << count << endl;

            k++;

        }

    }

    return ;

}

巴特西

POJ1328贪心

最新文章

热门文章