网站开发公司开发过程,外贸综合服务网站建设,nginx缓存wordpress,网站建设大师文章目录 反悔贪心力扣题目列表630. 课程表 III871. 最低加油次数LCP 30. 魔塔游戏2813. 子序列最大优雅度 洛谷题目列表P2949 [USACO09OPEN] Work Scheduling GP1209 [USACO1.3] 修理牛棚 Barn RepairP2123 皇后游戏#xff08;#x1f6b9;省选/NOI− TODO#xff09; 相关… 文章目录 反悔贪心力扣题目列表630. 课程表 III871. 最低加油次数LCP 30. 魔塔游戏2813. 子序列最大优雅度 洛谷题目列表P2949 [USACO09OPEN] Work Scheduling GP1209 [USACO1.3] 修理牛棚 Barn RepairP2123 皇后游戏省选/NOI− TODO 相关链接 反悔贪心
思路是无论当前的选项是否最优都接受然后进行比较如果选择之后不是最优了则反悔舍弃掉这个选项否则正式接受。如此往复。
力扣题目列表
630. 课程表 III
https://leetcode.cn/problems/course-schedule-iii/description/?envTypedaily-questionenvId2023-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]);// 最大堆PriorityQueueInteger 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 positioni1 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]);PriorityQueueInteger 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中存放目前遇到的负数PriorityQueueInteger 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;SetInteger s new HashSet();DequeInteger 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;PriorityQueueInteger 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();PriorityQueueLong 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 场周赛⭐反悔贪心
