【算法】反悔贪心-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】反悔贪心。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

反悔贪心

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

力扣题目列表

630. 课程表 III

https://leetcode.cn/problems/course-schedule-iii/description/?envType=daily-question&envId=2023-09-11

【算法】反悔贪心,算法,算法,反悔贪心,贪心

提示:
1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104

解法看注释就很清楚了。
【算法】反悔贪心,算法,算法,反悔贪心,贪心

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按照截止时间从小到大排序
        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 d = c[0], t = c[1];
            if (day + d <= t) {
                // 如果可以学，直接学
                day += d;
                pq.offer(d);
            } else if (!pq.isEmpty() && pq.peek() > d) {
                // 如果不可以学，检查已经选了的课程中有没有耗时更长的替换掉
                day -= pq.poll() - d;
                pq.offer(d);
            }
        }
        // 最后的答案就是队列中已选课程的数量
        return pq.size();
    }
}

871. 最低加油次数

https://leetcode.cn/problems/minimum-number-of-refueling-stops/

【算法】反悔贪心,算法,算法,反悔贪心,贪心
提示：
1 <= target, startFuel <= 10^9
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 10^9

按照加油站的出现顺序排序。
用堆维护目前可以加的油，每次路过一个加油站先不加而是放入优先队列中，等到走不动了再一个个从大到小加油。

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        // 按照出现顺序排序
        Arrays.sort(stations, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int ans = 0, pos = startFuel;
        for (int[] s: stations) {
            if (pos >= target) return ans;
            int p = s[0], f = s[1];
            while (pos < p && !pq.isEmpty()) {
                pos += pq.poll();
                ans++;
            }
            if (pos < p) return -1;
            else pq.offer(f);
        }
        while (pos < target && !pq.isEmpty()) {
            pos += pq.poll();
            ans++;
        }
        return pos < target? -1: ans;
    }
}

LCP 30. 魔塔游戏

https://leetcode.cn/problems/p0NxJO/
【算法】反悔贪心,算法,算法,反悔贪心,贪心

提示：
1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5

先检查是否可以访问完全部房间，如果不可以直接返回-1。
如果不可以，每次遇到负数先放入优先队列中去，当血量不够时，再依次从小到大取出堆中的负数调换到队尾。

class Solution {
    public int magicTower(int[] nums) {
        if (Arrays.stream(nums).sum() < 0) return -1;
        int ans = 0;
        // pq中存放目前遇到的负数
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long s = 1;
        for (int x: nums) {
            s += x;
            if (x < 0) pq.offer(x);
            while (s <= 0) {
                // 每次把最小的移动到最后面去
                s -= pq.poll();
                ans++;
            }
        }
        return ans;
    }
}

2813. 子序列最大优雅度

https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/description/

【算法】反悔贪心,算法,算法,反悔贪心,贪心

提示：
1 <= items.length == n <= 10^5
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 10^9
1 <= categoryi <= n
1 <= k <= n

按照利润从大到小排序。
i < k 时直接加入，如果有重复的类别就将当前元素放入栈中（因为是从大到小枚举，所以栈顶一定是利润最小的）
当 i > k 时，如果当前元素还没有出现过，就可以尝试替换掉重复类型中利润最小的元素。

class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        // 按利润从大到小排序
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        long ans = 0, totalProfit = 0;
        Set<Integer> s = new HashSet<>();
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < items.length; ++i) {
            int p = items[i][0], c = items[i][1];
            if (i < k) {
                totalProfit += p;
                if (s.contains(c)) stk.push(p);
                s.add(c);
            } else if (!stk.isEmpty() && !s.contains(c)) {
                totalProfit -= stk.pop() - p;
                s.add(c);
            }
            ans = Math.max(ans, totalProfit + (long)s.size() * s.size());
        }

        return ans;
    }
}

注意代码中的 s.add(c); 不能提出 if-else 之外，否则会影响答案。

洛谷题目列表

P2949 [USACO09OPEN] Work Scheduling G

https://www.luogu.com.cn/problem/P2949
【算法】反悔贪心,算法,算法,反悔贪心,贪心

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] g = new int[n][2];
        for (int i = 0; i < n; ++i) {
            g[i][0] = sc.nextInt();
            g[i][1] = sc.nextInt();
        }
        // 按照截止时间从小到大排序
        Arrays.sort(g, (a, b) -> a[0] - b[0]);
        long ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] p: g) {
            // 如果当前工作不超时  加入答案和优先队列中
            if (pq.size() < p[0]) {
                pq.offer(p[1]);
                ans += p[1];
            } else if (!pq.isEmpty() && p[1] > pq.peek()) {
                // 当前工作超时 和已经选了的工作中最小的交换
                ans += p[1] - pq.poll();
                pq.offer(p[1]);
            }
        }
        System.out.println(ans);
    }
}

P1209 [USACO1.3] 修理牛棚 Barn Repair

https://www.luogu.com.cn/problem/P1209

【算法】反悔贪心,算法,算法,反悔贪心,贪心

记得要对输入数据排序！

import java.io.BufferedInputStream;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sin = new Scanner(new BufferedInputStream(System.in));
        int m = sin.nextInt(), s = sin.nextInt(), c = sin.nextInt();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        int[] a = new int[c];
        long last = -1, ans = c;
        m--;
        for (int i = 0; i < c; ++i) {
            a[i] = sin.nextInt();
        }
        Arrays.sort(a);
        for (int i = 0; i < c; ++i) {
            int p = a[i];
            if (last != -1 && last < p - 1) {
                pq.add(p - last - 1);
                m--;
            }
            last = p;
        }
        while (m < 0 && !pq.isEmpty()) {
            m++;
            ans += pq.poll();
        }
        System.out.println(ans);
    }
}