贪心：PIPI渡江

客官°小女子只卖身不卖艺 2023-10-06 20:26 4阅读 0赞

## 贪心 ：PIPI渡江 ##

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

*  贪心 ：PIPI渡江
 *   *   *  问题：
         *  思路：
         *  代码：

#### 问题： ####

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

#### 思路： ####

我们可以在读取数据时就进行处理，设用ans表示可以渡江的分身数，对于`x >= d`的分身，第一次跳跃就可以渡江，ans++；对于`x < d && x + y >= d`的分身，第一次跳跃虽不能渡江，但可以踩别人渡江，我们称这些分身为被选中的分身；对于`x < d && x + y < d`的分身，它们是不可能渡江的，只能当垫脚石被别人踩，将其称为垫脚石分身。  
  设被选中的分身第二次跳跃的距离为y，那么它需要一个垫脚石先跳`d - y`的距离，而被选中的分身是一定能跳过这个距离的（因为它的x >= d - y），垫脚石分身需要被合理使用，我们的贪心策略为选择第一跳`>= d - y`且最接近d - y的垫脚石分身与其配对，这样我们就没有浪费垫脚石分身的跳跃能力，选择了最佳的配对垫脚石。  
  我们先让被选中的分身与垫脚石分身进行配对，若之后被选中的分身有剩余，则需要在剩余的被选中的分身中进行两两配对。设某一个被选中的分身第一跳的距离为x1，那么只需要另一个被选中的分身第一跳的距离`x2 >= x1`即可，只要让渡江分身能跳出第一跳，那么它就能渡江。那么剩余的被选中分身是一定能两两配对的（因为它们能按x排序，也就是说对于每个分身，一定有另一个分身能让它踩）。  
  先对被选中的分身和垫脚石分身进行配对，记录配对成功的数量count，设被选中分身数目为num，那么剩下的被选中分身中能配对成功的数量即为`(num - count) / 2`

#### 代码： ####

**需注意的点** ：

*  由于我们只需要被选中分身的y，因此被选中分身用一个long\[\]数组保存其y值就好了，不需要创建类，也不需要x,y都保存。
 *  被选中的分身与垫脚石分身进行配对时，我们需遍历被选中分身，然后在垫脚石分身中找到`>= d - y`且最接近d - y的，也就是ceil操作。那么我们用什么数据结构保存垫脚石分身呢？与第一点同理，我们只需要垫脚石分身的x，因此不用保存垫脚石分身的y，TreeSet提供了ceil、floor等方法，但TreeSet只能保存不重复的数据，而y值是肯定有重复的。TreeSet只能保存不重复的数据，这一点几乎是无解的，我们可以在其构造器中提供一个实现了Comparator接口的类，并重写compare方法，使其不返回0，但这样是能强行保存重复数据了，但之后的get和remove方法就都失效了，具体为什么可以看这个博客：[Java中TreeSet添加重复元素问题][Java_TreeSet]。那么我们只能退而求其次，使用TreeMap<Long, Long>来表示垫脚石分身，key为x，value为x出现的次数。使用TreeMap的`ceilingKey`方法找到我们需要的垫脚石分身，并将其value减一，当value减为0时，我们删去这个元素。

import java.util.*;
    
    public class Main {
        
        static TreeMap<Long, Long> dead = new TreeMap<>();
        static long[] choosen = new long[1000002];
        public static void main(String[] args) {
        
            int n, i, choseNum = 0, ans = 0, useDeadCount = 0;
            long d, x, y;
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            d = scanner.nextLong();
            for (i = 0;i < n;i++) {
        
                x = scanner.nextLong();
                y = scanner.nextLong();
                if (x >= d) {
        
                    ans++;
                } else if (x + y >= d) {
        
                    choosen[choseNum] = y;
                    choseNum++;
                } else {
        
                    if (dead.get(x) != null) {
        
                        dead.put(x, dead.get(x) + 1);
                    } else {
        
                        dead.put(x, 1L);
                    }
                }
            }
            for (i = 0;i < choseNum && dead.size() > 0;i++) {
        
                Long index = dead.ceilingKey(d - choosen[i]);
                if (index != null) {
        
                    ans++;
                    useDeadCount++;
                    if (dead.get(index) - 1 == 0) {
        
                        dead.remove(index);
                    } else {
        
                        dead.put(index, dead.get(index) - 1);
                    }
                }
            }
            ans += (choseNum - useDeadCount) / 2;
            System.out.println(ans);
        }
    
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7c4bb3d51e79451eb93593aad1f144cd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/72617b1bf98e47f7834fb4da45d9f2e6.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[Java_TreeSet]: https://blog.csdn.net/qq_36334929/article/details/116524984?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~aggregatepage~first_rank_ecpm_v1~rank_v31_ecpm-1-116524984.pc_agg_new_rank&utm_term=treeset%E6%B7%BB%E5%8A%A0%E9%87%8D%E5%A4%8D%E5%80%BC&spm=1000.2123.3001.4430