8.反悔贪心

反悔贪心

https://www.cnblogs.com/Doge297778/p/16503103.html

反悔贪心基于贪心,即一开始也是按照某一贪心策略执行贪心。但是反悔贪心引入了一个新操作,即反悔
我们可以在贪心的过程中做出一些处理,将我们假想/构造的代表反悔选项的决策同时插入决策集合,然后继续按照步骤贪心。
若之后选择了已经构造的反悔选项,代表撤销(反悔)之前的的决策而选用新的更优决策。

所以,反悔贪心的基本思想是:既然这次不一定是最优,那么就先放着,如果以后找到更优的再取消这次操作,选取更优的操作
这样的话只要保证当前最优就可以了,因为以后的更优就会反悔

维护当前最优和以后的反悔通常用堆实现。

反悔操作一个经典的应用就是网络流中寻找增广路时“建反边”的操作。

相似题目:

630. 课程表 III

困难

courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续durationi 天课,并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1:

输入:courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出:3
解释:
这里一共有 4 门课程,但是你最多可以修 3 门:
首先,修第 1 门课,耗费 100 天,在第 100 天完成,在第 101 天开始下门课。
第二,修第 3 门课,耗费 1000 天,在第 1100 天完成,在第 1101 天开始下门课程。
第三,修第 2 门课,耗时 200 天,在第 1300 天完成。
第 4 门课现在不能修,因为将会在第 3300 天完成它,这已经超出了关闭日期。

示例 2:

输入:courses = [[1,2]]
输出:1

示例 3:

输入:courses = [[3,2],[4,3]]
输出:0

提示:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104

https://leetcode.cn/problems/course-schedule-iii/solutions/2436667/tan-xin-huan-neng-fan-hui-pythonjavacgoj-lcwp/?envType=daily-question&envId=2023-09-11

如果能增大课程数量,就增大课程数量,如果不能增大课程数量,就在保持课程数量不变的前提下,尝试减少总时长,使得后续增大课程数量的概率增加。

经验告诉我们,在准备期未考试的时候,先考的课程先准备。同理lastDay 越早的课程,应当越早上完。但是,有的课程 duration 比较长,上完需要花很多时间,可能把这些时间花在其它课程,早就上完好几门课了。

看上去,找不到一个合适的贪心策略。别放弃!顺着这个思路,如果我们可以**[反悔]**呢?

按照 lastDay 从小到大排序,然后遍历 courses。比如先上完duration = 7 的课和 duration = 10 的课,后面遍历到了 duration = 4的课,但受到 lastDay 的限制,无法上 duration = 4 的课。此时,我们可以[撤销]前面 duration 最长的课,也就是 duration = 10 的课,这样就可以上 duration = 4 的课了! 虽然能上完的课程数目没有变化,但是由于我们多出了 10 - 4 = 6 天时间,在后续的遍历中,更有机会上完更多的课程。

在上面的讨论中,我们需要维护一个数据结构,来帮助我们快速找到duration 最长的课程。这可以用最大堆解决。

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按照 lastDay 从小到大排序
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        // 维护最大堆,按照已经学习的课程持续时间排序
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int day = 0; // 已消耗时间
        for(int[] c : courses){
            int duration = c[0], lastDay = c[1];
            if(day + duration <= lastDay){ // 没有超过 lastDay,直接学习
                day += duration;
                pq.offer(duration);
            }else if(!pq.isEmpty() && duration < pq.peek()){  // 该课程的时间比之前的最长时间要短
                // 反悔,撤销之前 duration 最长的课程,改为学习该课程
                // 节省出来的时间,能在后面上完更多的课程
                day -= pq.poll() - duration;
                pq.offer(duration);
            }
        }
        return pq.size();
    }
}

2813. 子序列最大优雅度

困难

给你一个长度为 n 的二维整数数组 items 和一个整数 k

items[i] = [profiti, categoryi],其中 profiticategoryi 分别表示第 i 个项目的利润和类别。

现定义 items子序列优雅度 可以用 total_profit + distinct_categories*2 计算,其中 total_profit 是子序列中所有项目的利润总和,distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中,找出 最大优雅度

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

**注意:**数组的子序列是经由原数组删除一些元素(可能不删除)而产生的新数组,且删除不改变其余元素相对顺序。

示例 1:

输入:items = [[3,2],[5,1],[10,1]], k = 2
输出:17
解释:
在这个例子中,我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ,子序列包含 2 种不同类别 [2,1] 。
因此,优雅度为 13 + 22 = 17 ,可以证明 17 是可以获得的最大优雅度。 

示例 2:

输入:items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出:19
解释:
在这个例子中,我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ,items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ,子序列包含 3 种不同类别 [1, 2, 3] 。 
因此,优雅度为 10 + 32 = 19 ,可以证明 19 是可以获得的最大优雅度。

示例 3:

输入:items = [[1,1],[2,1],[3,1]], k = 3
输出:7
解释:
在这个例子中,我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6,子序列包含 1 种不同类别 [1] 。
因此,最大优雅度为 6 + 12 = 7 。

提示:

  • 1 <= items.length == n <= 105
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 109
  • 1 <= categoryi <= n
  • 1 <= k <= n
class Solution {
    /*
    找到一个 base, 先选最大的 k 个利润,这可能是一个答案
    
    考虑下一个项目要不要选
    由于利润从大到小排序,利润和 total profit 不会变大
    所以重点就在 distinct_categories 能不能变大? (考虑变化量)

    分类讨论:
    1. 如果新添加的项目的类别之前选过了,那么 distinct_categories 不会变大
    2. 如果新添加的项目的类别之前没选过(没出现过)
    2.1 如果移除的项目的类别只有一个,那么 distinct_categories-1+1,不变,不行
    2.2 如果移除的项目的类别有多个,那么 distinct_categories+1,这种情况就是可以的
        - 选一个利润最小的移除,用一个栈维护
    */
    public long findMaximumElegance(int[][] items, int k) {
        Arrays.sort(items, (a, b) -> b[0] - a[0]); // 按利润从大到小排序
        long ans = 0, totalProfit = 0;
        Set<Integer> vis = new HashSet<>();
        // 因为从大到小枚举的利润,所以栈顶元素一定是最小的利润值
        Deque<Integer> duplicate = new ArrayDeque<>(); // 重复类别的利润
        for(int i = 0; i < items.length; i++){
            int profit = items[i][0], category = items[i][1];
            if(i < k){
                totalProfit += profit;
                if(!vis.add(category)) // 重复类别
                    duplicate.push(profit);
            }else if(!duplicate.isEmpty() && vis.add(category)){
                totalProfit += profit - duplicate.pop(); // 选一个重复类别中的最小利润替换
            }// else:比前面的利润小,而且类别还重复了,
            //      选它只会让 totalProfit 变小,vis.size() 不变,优雅度不会变大
            ans = Math.max(ans, totalProfit + (long)vis.size() * vis.size());
        }
        return ans;
    }
}

871. 最低加油次数

困难

汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。

沿途有加油站,用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处,并且有 fueli 升汽油。

假设汽车油箱的容量是无限的,其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。

为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1

注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。

示例 1:

输入:target = 1, startFuel = 1, stations = []
输出:0
解释:可以在不加油的情况下到达目的地。

示例 2:

输入:target = 100, startFuel = 1, stations = [[10,100]]
输出:-1
解释:无法抵达目的地,甚至无法到达第一个加油站。

示例 3:

输入:target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出:2
解释:
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站,消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后,从 10 英里处的加油站开到 60 英里处的加油站(消耗 50 升燃料),
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠,所以返回 2 。

提示:

  • 1 <= target, startFuel <= 109
  • 0 <= stations.length <= 500
  • 1 <= positioni < positioni+1 < target
  • 1 <= fueli < 109
class Solution {
    /**
    题目思路:
    - 将路上的一个个加油站 视为 一桶桶的油,每次经过的时候,就把油带上放后备箱;
    - 当油不够的时候,取出后备箱所带的 最多的那桶油 加进油箱
    - 这样以来,如若油箱和后备箱的油加起来都不够,那么就到不了了
    */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        // 使用优先队列,承装所经过加油站的油
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        int ans = 0, len = stations.length;
        if (len < 1) return startFuel < target ? -1 : 0;
        int fuel = startFuel;// 加进油箱的油(含使用过的)
        // 经过可以到达的所有的加油站,背上里面的油
        for (int i = 0; i < len; i ++) {
            while (fuel < stations[i][0]) {
                Integer add = q.poll();
                if (add == null) return -1;
                fuel += add;
                ans ++;
            }
            q.offer(stations[i][1]);
        }
        // 已经经过所有的加油站仍未到达,则用车油箱和后备箱里的所剩的fuel,以期到达
        while (fuel < target) {
            Integer add = q.poll();
            if (add == null) return -1;
            fuel += add;
            ans ++;
        }
        return ans;
    }
}

LCP 30. 魔塔游戏

中等

小扣当前位于魔塔游戏第一层,共有 N 个房间,编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums,其中正数表示道具补血数值,即血量增加对应数值;负数表示怪物造成伤害值,即血量减少对应数值;0 表示房间对血量无影响。

小扣初始血量为 1,且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪,为保证血量始终为正值,小扣需对房间访问顺序进行调整,每次仅能将一个怪物房间(负数的房间)调整至访问顺序末尾。请返回小扣最少需要调整几次,才能顺利访问所有房间。若调整顺序也无法访问完全部房间,请返回 -1。

示例 1:

输入:nums = [100,100,100,-250,-60,-140,-50,-50,100,150]

输出:1

解释:初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。

示例 2:

输入:nums = [-200,-300,400,0]

输出:-1

解释:调整访问顺序也无法完成全部房间的访问。

提示:

  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5

https://leetcode.cn/problems/p0NxJO/solutions/702009/javatan-xin-you-xian-dui-lie-shuang-bai-3r7fb/

class Solution {
    /**
    首先,我们计算一遍所有回合之后的血量,如果是负数,则直接返回-1 
    然后我们模拟过程,将之前扣减的血量都放入优先队列中,
    每次快死之前,就取出堆顶的元素(扣最多的血)给自己加上,
    这样的贪心思想能保证我们移动到尾部的元素是最少的。
     */
    public int magicTower(int[] nums) {
        int sum = 1;
        for(int num : nums) sum += num;
        if(sum <= 0) return -1;

        long blood = 1;
        // 维护堆顶血量最小(注意是元素都是负数)
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a-b);
        int last = 0;
        for(int num : nums){
            if(num < 0){
                pq.offer(num);
                // 这回合过后就要死了,需要把前面扣最多的血移到最后去
                if(blood + num <= 0){
                    last++; // 移动次数加一
                    blood -= pq.poll();// 加回之前扣除最多的血量
                }
            }
            blood += num;
        }
        return last;
    }
}