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 <= 1041 <= 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]，其中 profiti 和 categoryi 分别表示第 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 <= 105items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 1091 <= categoryi <= n1 <= 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 <= 1090 <= stations.length <= 5001 <= positioni < positioni+1 < target1 <= 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;
}
}