当前位置: 首页 > news >正文

【算法】反悔贪心

文章目录

  • 反悔贪心
  • 力扣题目列表
    • 630. 课程表 III
    • 871. 最低加油次数
    • LCP 30. 魔塔游戏
    • 2813. 子序列最大优雅度
  • 洛谷题目列表
    • P2949 [USACO09OPEN] Work Scheduling G
    • P1209 [USACO1.3] 修理牛棚 Barn Repair
    • P2123 皇后游戏(🚹省选/NOI− TODO)
  • 相关链接

反悔贪心

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

力扣题目列表

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);}
}

每次将空格记录在优先队列中,当木板数量不够时,从小到大取出优先队列中的空格依次填上。

P2123 皇后游戏(🚹省选/NOI− TODO)

https://www.luogu.com.cn/problem/P2123
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入代码片

相关链接

【力扣周赛】第 357 场周赛(⭐反悔贪心)

http://www.lryc.cn/news/163649.html

相关文章:

  • Hadoop的安装和使用,Windows使用shell命令简单操作HDFS
  • ubuntu上ffmpeg使用framebuffer显示video
  • 82 # koa-bodyparser 中间件的使用以及实现
  • 计算一串输出数字的累加和
  • python包导入原理解析
  • MNIST手写数字辨识-cnn网路 (机器学习中的hello world,加油)
  • 论文笔记《3D Gaussian Splatting for Real-Time Radiance Field Rendering》
  • 数据库管理系统,数据库,sql的基本介绍以及它们之间的关系
  • 【Flowable】Springboot使用Flowable(一)
  • 戳泡泡小游戏
  • Redis缓存
  • mysql 插入更新数据
  • 系统架构设计高级技能 · 软件产品线
  • C语言学习系列-->字符函数和字符串函数
  • 尖端AR技术如何在美国革新外科手术实践?
  • 【木板】Python实现-附ChatGPT解析
  • 第一章:绪论
  • C++面试知识点总结
  • 从智能手机到智能机器人:小米品牌的高端化之路
  • 深度学习推荐系统(八)AFM模型及其在Criteo数据集上的应用
  • 【Spring】aop的底层原理
  • 微信小程序开发---基本组件的使用
  • SpringBoot国际化配置组件支持本地配置和数据库配置
  • Shell编程之sort
  • windows docker 容器启动报错:Ports are not available
  • 300. 最长递增子序列
  • DNS(域名解析系统)
  • 解决jsp/html界面跳转servlet出现404错误的方法
  • catface,使用Interface定义Controller,实现基于Http协议的RPC调用
  • Linux:LVS (NAT群集搭建)