贪心算法学习(喷水装置)
程序员文章站
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); } }