小嗷犬

题解

/ 注册

全部文章 / 题解（共8篇）

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

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

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

2023-08-18

3 595

题解 | #网络优化#

考察知识点：贪心、优先队列读入服务器的信息，按照 (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

西南财经大学·奇点工作室·程序设计部暑期训练营第三次课后习题题解

A. 递归函数的次数题目链接：A. 递归函数的次数考察知识点：递归、滚动数组递归函数调用次数满足递推式 an=an−1+an−2+an−3+1a_n = a_{n-1} + a_{n-2} + a_{n-3} + 1an=an−1+an−2+an−3+1，其中 a1=a2=a3=1a_...

C++ 贪心二分查找模拟前缀和递归枚举分治数学字符串

2023-08-07

3 543

题解 | #牛牛的朋友#

考察知识点：贪心考虑两头牛时的情况，有以下 4 种移动方式：两头牛同时向左移动：距离不变两头牛同时向右移动：距离不变左边的牛向左移动，右边的牛向右移动：距离增大左边的牛向右移动，右边的牛向左移动：距离可能减小其中前两种情况对答案没有影响，第三种情况可以直接忽略，第四种情况需要考虑。 ...

C++ 贪心

2023-08-02

5 457

题解 | #牛牛的排序#

考察知识点：贪心由题易知，最坏情况下也只需要 3 次排序即可，因此考虑 0 ~ 3 次排序的情况：当数组本身有序时，不需要排序，输出 0；当最大值或最小值已经就位时，只需要排序 1 次，输出 1；当最大值与最小值都不在头尾时，需要排序 2 次，输出 2；当最大值位于头部，最小值位于尾部时...

C++ 贪心

2023-08-02

2 384