首页 > 代码库 > 贪心--区间覆盖及区间选点问题

贪心--区间覆盖及区间选点问题

2024-07-14 04:49:58   228人阅读

区间覆盖：

数轴上有若干区间，选用最少的线段覆盖指定区间。

区间选点：选用最少的区间使每个区间内至少有一个点

样题1：

J - Muddy roads
 
Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Description
Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools. 

Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely. 

Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.

Input

* Line 1: Two space-separated integers: N and L 

* Lines 2..N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap. 

Output

* Line 1: The miminum number of planks FJ needs to use.

Sample Input

3 31 613 178 12

Sample Output

5

Hint

INPUT DETAILS: 

FJ needs to use planks of length 3 to cover 3 mud pools. The mud pools cover regions 1 to 6, 8 to 12, and 13 to 17. 

OUTPUT DETAILS: 

FJ can cover the mud pools with five planks of length 3 in the following way: 
                   111222..333444555....
                   .MMMMM..MMMM.MMMM....
                   012345678901234567890


题目意思是要用最少的定长木板将指定区间完全覆盖
分析：只要选取最少的线段覆盖指定区间就行。那么先将区间按左端升序排列，每次从最左端开始用线段覆盖，标记所选线段的末端位置，使在指定区间尽量使线段紧密排列就可以了。
代码实现：
//先按开始坐标升序排序，接着记录每个木板结束的位置，尽量挨着铺#include<cstring>#include<cstdio>#include<algorithm>const int N = 10010;using namespace std;struct ss{int s;int e;}m[N];bool cmp(ss x,ss y){     return x.s < y.s;}int main(){     int n,l,last,ans;     while(~scanf("%d%d",&n,&l)){               ans = 0;          for(int i = 0; i < n; i ++){               scanf("%d%d",&m[i].s,&m[i].e);          }          sort(m,m+n,cmp);          last = -1;          int len;          for(int i = 0; i < n; i ++){             if(last >= m[i].e)  continue;             if(last > m[i].s){               len = m[i].e-last;               int k = (len+l-1)/l;               //printf("%d %d",k,last);               last += k*l;               ans += k;             }            else{               len = m[i].e - m[i].s;               int k = (len+l-1)/l;              // printf("hh %d %d %d\n",k,last,m[i].s);               last = m[i].s+k*l;               ans += k;            }           // printf("%d\n",last);          }          printf("%d\n",ans);     }return 0;}
View Code

 

样题2：

I - Radar Installation
Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u
 
Appoint description: 

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. 

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates. 

Figure A Sample Input of Radar Installations


Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. 

The input is terminated by a line containing pair of zeros 

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input

3 21 2-3 12 11 20 20 0

Sample Output

Case 1: 2Case 2: 1

 

 

这道题是用圆心在X轴上且给定半径的一些圆将X轴上方的给定点覆盖，求圆的最小数量

这道题WA了好几次。。贪心还是要策略啊

分析：

 这道题表面上是要用面去覆盖点的问题，但是二维平面上的贪心策略很难实现。其实可以换一种思考方式：以每个岛屿对应的点为圆心，给定圆的半径为半径做圆交X轴于两点left和right，那么区间[left,right]就对应着这个点，这样的话问题就变成了用尽量少的满足条件的区间覆盖全部的点，也就是使每个区间里至少有一个点。
代码实现：
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>const int N = 1010;using namespace std;#define inf ox3f3f3f3fstruct ss{double x;double y;double s;//该点对应区间的左端点double e;//该点对应区间的右端点}p[N];bool cmp(ss x, ss y){     if(x.e == y.e)     return x.s < y.s;     return x.e<y.e;}int flag[N];int main(){     //freopen("in.txt","r",stdin);    // freopen("out.txt","w",stdout);  int  n,t = 0,ans;  double d;  while(scanf("%d%lf",&n,&d) && n+d){          ++t;          ans = 0;       //  memset(ans,0,sizeof(ans));         memset(flag,0,sizeof(flag));     for(int i = 0; i < n; i ++){      scanf("%lf%lf",&p[i].x,&p[i].y);      double len = sqrt(d*d - p[i].y*p[i].y);      p[i].s = p[i].x - len;      p[i].e = p[i].x + len;     }     sort(p,p+n,cmp);     int kk = 1;     for(int i = 0; i < n; i ++){          if(p[i].y > d){//当前点的纵坐标超出雷达能达到的的最大范围           kk = 0;           break;          }          if(flag[i]) continue;              flag[i] = 1;              for(int j = i+1; j < n; j ++)//找出该区间可以覆盖的所有点             if(p[j].s <= p[i].e){               flag[j] = 1;              }              ans ++;     }     if(kk)     printf("Case %d: %d\n",t,ans);     else     printf("Case %d: -1\n",t);     }return 0;}
View Code

 

 

 

 

贪心--区间覆盖及区间选点问题


联系
我们