ACM知识点 之 贪心(5)最小区间覆盖问题

  • Post author:
  • Post category:其他


关于区间相关贪心算法的讨论,

点击这里,有一份详细的资料,还有几个问题没有说到 《浅谈信息学竞赛中的区间问题》



在贪心算法的层面上,我们能够进行解决的区间覆盖,指的就是

最小区间覆盖问题




问题描述为:

给定n个区间和一个范围[a, b],选择尽量少的区间,使得[a, b]能够被完全覆盖。

贪心的策略我们可以思考一下:

  1. 对于当前区间[a,b]来说,选择的下一个区间的左端点值a2一定不会大于b,否则就不能完成

    “覆盖”

    这一操作。
  2. 对于当前区间[a,b]来说,如果有多个区间都满足条件1,那么一定选择

    右端点最大

    的区间,否则就不能满足

    “最小”

    这一目的。

也不是很难嘛~~


同样的,我们需要对区间进行排序,并且排序方法还是那样,按照左右端点都无所谓。反正需要的只是一个有序的列表而已。

那么我们可以尝试着写出如下伪代码:

while(剩余区间数目不为0)
{
    if(总长度已经超出覆盖范围)
    {
        结束循环;
    }
    for(循环查找符合条件的下一个最大区间);
    if(找到了)
    {
        答案数+1;
        总长度 += 最大能切换的区间长度;
    }else
    {
        表示不能完全覆盖,退出循环,答案数 = 0;
    }
}

所以,看题



NYOJ 12

                            喷水装置(二)
                时间限制:3000 ms  |  内存限制:65535 KB
                                难度:4


描述



有一块草坪,横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置,每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置,把整个草坪全部润湿。


输入



第一行输入一个正整数N表示共有n次测试数据。


每一组测试数据的第一行有三个整数n,w,h,n表示共有n个喷水装置,w表示草坪的横向长度,h表示草坪的纵向长度。


随后的n行,都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标(最左边为0),ri表示该喷水装置能覆盖的圆的半径。


输出



每组测试数据输出一个正整数,表示共需要多少个喷水装置,每个输出单独占一行。


如果不存在一种能够把整个草坪湿润的方案,请输出0。


样例输入



2


2 8 6


1 1


4 5


2 10 6


4 5


6 5


样例输出



1


2


这道题题意不难理解,主要在于要把圆心坐标和半径转换成在指定范围内矩形的长和宽。之后的可以按照我们上面的分析来了。

AC代码如下:


/*
************************************
Title: NYOJ 12 - 喷水装置(二)
************************************
Date:2015/07/24
************************************
author:刘旭
************************************
Memory:388KB
Time:0ms
************************************
*/

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

#define INF 1e-6    //双精度浮点数趋近于0的值
#define MAX 10005

struct Node {
    double left;
    double right;
} map[MAX];

int num_input = 0;
int length = 0;
int width = 0;

int cmp(Node a,Node b)
{
    if(a.left !=  b.left) { //这里按左端点排序比较方便
        return a.left < b.left;
    }

    return a.right < b.right;
}

double calue(int r)
{
    double res;
    res = (double)r*r - (double)width*width/4.0;

    if(res >= INF) {
        res = sqrt(res);
    } else {
        res = 0;
    }

    return res;
}

int main()
{
    int time = 0;
    scanf("%d", &time);
    while(time--) {
        scanf("%d%d%d", &num_input, &length, &width);

        int a = 0;
        int b = 0;
        double res = 0;
        for(int i = 0; i < num_input; i++) {
            scanf("%d %d",  &a, &b);
            res = calue(b);
            map[i].left = a - res;
            map[i].right = a + res;
        }

        sort(map, map+num_input, cmp);

        double sum = 0;
        int ans = 0;
        while(sum < length) {
            double num_max = 0;
            for(int i = 0; i < num_input && map[i].left <= sum; i++) {
                num_max = max(num_max, map[i].right-sum);
            }

            if(0 == num_max) {
                ans = 0;
                break;
            } else {
                sum += num_max;
                ans++;
            }
        }

          printf("%d\n",ans);
    }
    return 0;
}




版权声明:本文为xia842655187原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。