区间贪心：最小区间覆盖问题、PIPI的高速公路

刺骨的言语ヽ痛彻心扉 2023-10-06 20:19 30阅读 0赞

## 区间贪心：最小区间覆盖问题、PIPI的高速公路 ##

#### 文章目录 ####

*  区间贪心：最小区间覆盖问题、PIPI的高速公路
 *   *   *  问题1：
         *  思路：
         *  代码：
         *  问题2：
         *  思路：
         *  代码：

#### 问题1： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

本题是区间贪心的一种：在满足覆盖\[L,R\]区间的情况下，最少能选择多少个区间  
  我们可以将线段（区间）按左端点从小到大排序，我们的贪心策略是每次所选择的区间使后面预留的空间最小，即尽可能多地占用\[L,R\]中的空间。为此，我们可以定义右极限rLimit，表示当前所遍历到的合法区间中r的最大值，初始化为L，每次我们从合法的备选区间（即`l <= rLimit`）中找出右端点r最大的区间并选择该区间，接着更新rLimit，使`rLimit = r`，持续该过程，直到rLimit >= R，我们便用最少的区间数覆盖了\[L,R\]

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static List<Region> array = new ArrayList<>();
        public static void main(String[] args) {
        
            int i, n, L, R, li, ri, ans, rLimit, rMax;
            boolean flag;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                ans = 0;
                array.clear();
                n = scanner.nextInt();
                L = scanner.nextInt();
                R = scanner.nextInt();
                for (i = 0;i < n;i++) {
        
                    li = scanner.nextInt();
                    ri = scanner.nextInt();
                    if (ri < L || li > R) {
        
                        continue;
                    }
                    array.add(new Region(li, ri));
                }
                if (array.size() == 0) {
        
                    System.out.println(-1);
                    continue;
                }
                Collections.sort(array, new Comparator<Region>() {
        
                    @Override
                    public int compare(Region o1, Region o2) {
        
                        return o1.l - o2.l;
                    }
                });
                rLimit = L;
                rMax = L;
                for (i = 0;i < array.size();i++) {
        
                    flag = false;
                    while (i < array.size() && array.get(i).l <= rLimit) {
        
                        rMax = Math.max(rMax, array.get(i).r);
                        i++;
                        flag = true;
                    }
                    if (flag) {
        
                        i--;
                        rLimit = rMax;
                        ans++;
                    }
                    if (rLimit >= R) {
        
                        break;
                    }
                }
                System.out.println(rLimit >= R ? (ans == 0 ? -1 : ans) : -1);
            }
        }
    
    
    }
    
    class Region {
        
        public int l;
        public int r;
    
        public Region(int l, int r) {
        
            this.l = l;
            this.r = r;
        }
    }

#### 问题2： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 思路： ####

该题乍一看好像和区间没什么关系，但我们需要发现对于每个村庄(x,y)，到其距离不超过D的出口的x坐标值处于一个区间内，该区间为`[x - sqrt(d ^ 2 - y ^ 2)，x + sqrt(d ^ 2 - y ^ 2)`。  
  于是，这道题被转化为了区间贪心的问题。成为了区间贪心的一种：在满足每个区间中至少有一个点（出口）情况下，最少能选择多少个点（出口）？我们的贪心策略是使一个点（出口）尽可能多地处于不同区间内，即尽可能多的区间能共用一个点（出口）。  
  如何执行上述贪心策略呢？我们可以按区间的右端点从小到大对区间排序，定义右极限rLimit，初值为第一个区间的右端点，然后进行区间的遍历。若当前遍历到的区间的左端点<=rLimit，说明当前区间可以和前面的某些区间共用一个点（这是因为当前区间和前面的某些区间都满足左端点<=rLimit，且由于排序关系，右端点>=rLimit，也就是说这些区间存在公共的重叠部分，可以共用一个出口），若当前遍历的区间左端点>rLimit，说明当前区间和前面的区间不可共用一个点，所需出口数ans++，并更新rLimit的值为当前区间的右端点，重复上述过程直到遍历完所有区间。

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static Region[] array = new Region[1002];
        public static void main(String[] args) {
        
            int ans, i, n;
            double l, d, x, y, left, right, nextLeft, nextRight;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextDouble()) {
        
                ans = 0;
                l = scanner.nextDouble();
                d = scanner.nextDouble();
                n = scanner.nextInt();
                for (i = 0;i < n;i++) {
        
                    x = scanner.nextDouble();
                    y = scanner.nextDouble();
                    left = x - Math.sqrt(d * d - y * y);
                    right = x + Math.sqrt(d * d - y * y);
                    left = left > 0 ? left : 0;
                    right = right > l ? l : right;
                    array[i] = new Region(left, right);
                }
                Arrays.sort(array, 0, n, new Comparator<Region>() {
        
                    @Override
                    public int compare(Region o1, Region o2) {
        
                        if (o1.right - o2.right > 0) {
        
                            return 1;
                        }
                        return -1;
                    }
                });
                right = array[0].right;
                for (i = 0;i < n;i++) {
        
                    nextLeft = array[i].left;
                    nextRight = array[i].right;
                    if (nextLeft > right) {
        
                        right = nextRight;
                        ans++;
                    }
                }
                ans = n == 0 ? ans : ans + 1;
                System.out.println(ans);
            }
        }
    }
    
    class Region {
        
        public double left;
        public double right;
    
        public Region(double left, double right) {
        
            this.left = left;
            this.right = right;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/cf165660ddbe4204ab7f11d35c52b320.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/7dd748a7072f4a70b7d21a4479a26d81.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/045ac4df307140a5bb8d50c40fd84e53.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/903b45edc21a42759fdd162275aa7a69.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16