小嗷犬

分类

题解(39)

/ 注册

全部文章（共5篇）

题解 | #[NOIP2004]合并果子#

考察知识点：贪心、优先队列、哈夫曼树题目翻译一下就是个节点构成一棵二叉树，求这棵树的最小带权路径长度。哈夫曼树是带权路径长度最小的树，所以本题只需要构造一棵哈夫曼树即可。时间复杂度： #include <bits/stdc++.h> using namespace std; ...

C++ 贪心堆(优先队列) 哈夫曼树

2023-08-18

3 594

题解 | #网络优化#

考察知识点：贪心、优先队列读入服务器的信息，按照 (l, r, v) 升序排序，遍历每一位用户，为每一位用户分配符合条件的服务器中 r 最小的服务器，对应的服务器的 v 值减一，若成功为用户分配服务器，则答案 ans 加一。时间复杂度： #include <bits/stdc++.h>...

C++ 贪心堆(优先队列)

2023-08-18

3 437

题解 | #[JSOI2010]缓存交换#

考察知识点：贪心、优先队列模拟操作系统 MIN/OPT 换页机制，每次换页优先选择未来不会再访问的页或者在最长一段时间不会再访问的页（即当前缓存页中下次最晚访问的页），具体实现请见代码。理论上，MIN/OPT 换页机制是最优的内存换页机制，但是由于需要预知未来的访问情况，所以在实际应用中无法使...

C++ 贪心堆(优先队列)

2023-08-18

3 463

题解 | #[JSOI2007]建筑抢修#

考察知识点：贪心、优先队列读入每个建筑的信息，按照每个建筑修理的截止时间 t2 升序排序，然后依次将建筑修理的时间 t1 加入优先队列（大根堆），同时维护当前建筑修理的时间之和 time，当当前建筑修理完成后的时间大于截止时间时，如果当前建筑所需的修理时间 t1 小于优先队列顶端的建筑所需的修理时...

C++ 贪心堆(优先队列)

2023-08-18

2 438

题解 | #tokitsukaze and Soldier#

考察知识点：贪心、优先队列读入每个士兵的信息，按照士兵的 s[i] 值降序排序，然后依次将士兵战力加入优先队列（小根堆），同时维护当前士兵战力之和 cnt，当优先队列大小超过当前士兵的 s[i] 值时，将优先队列顶端的士兵战力（即最低战力）从 cnt 中减去，直到优先队列大小不超过当前士兵的 s[...

C++ 贪心堆(优先队列)

2023-08-18

2 454