欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪心算法学习(喷水装置)

程序员文章站 2023-12-28 23:52:10
...

1、区间覆盖问题(喷水装置)

    喷水装置这道题,将每个圆形区域,抽象成一个覆盖在草地上的矩形区域,选择一个最少的数量,使得喷洒面积刚好能够覆盖草地。(如红线部分)

    将所有区域按照左端点从大到小排序,依次处理每个区间,每次选择下一个区间的时候,要求选择能够覆盖当前区间的右端,并且保证下一个区间的右端是最大的,更新坐标,查找下一个。

    这道题需要一些抽象思维,特别是选择区间的时候,左右端点灵活变换。

这道题有一个坑:需要特判一下R<=w/2的情况。

贪心算法学习(喷水装置)

例题:https://loj.ac/problem/10002

AC代码:

#include<bits/stdc++.h>

using namespace std;

struct node{
    double x,y;
};
int cmp(const node &a,const node &b){
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y>b.y;
}
node a[20005];
int main()
{
    int t,n,l,w;
    scanf("%d",&t);

    while(t--){
        scanf("%d%d%d",&n,&l,&w);
        int len = 0;
        for(int i=0;i<n;i++)
        {
            int x,r;
            scanf("%d%d",&x,&r);
            if(r<=(w/2.0))
                continue;
            a[len].x = x - sqrt(r*r - (w/2.0)*(w/2.0));
            a[len++].y = x + sqrt(r*r - (w/2.0)*(w/2.0));
        }
        sort(a,a+len,cmp);

        double s = 0,t = 0;//s用于标记当前矩形框的右端,t用于查找下一个矩形框
        int sum = 0,flag = 0;
        while(t<l)
        {
            s = t;

            for(int i = 0;i<len;i++){//寻找下一个矩形框
                if(a[i].x>s)//下一个矩形框的左端不得超过当前矩形框的右端
                    break;
                if(a[i].y>t)//不断的去找更大的矩形框
                    t = a[i].y;
            }
            sum++;
            if(s == t && s<l)
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            printf("-1\n");
        else
            printf("%d\n",sum);

    }
}

 

上一篇:

下一篇: