贪心：PIPI渡江

文章目录

贪心：PIPI渡江

问题：

思路：

我们可以在读取数据时就进行处理，设用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添加重复元素问题。那么我们只能退而求其次，使用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);
    }

}