第六章 贪心
区间问题
排序,按左端点,或右端点,或双关键字排序
Huffman树
利用堆结构,调最小的两堆,合并
排序不等式
$$ t_1\left( n-1 \right) +t_2\left( n-2 \right) +\cdots +t_{n-1} $$
易知 $t$ 由小到大排序即可使得总和最小
绝对值不等式
$$ \left| a-x \right|+\left| b-x \right|\ge \left| a-x-\left( b-x \right) \right|=\left| a-b \right| $$
推公式
参考例题:AcWing 125. 耍杂技的牛 - AcWing
公式即,按照自身重量和承受能力之和进行排序,从小到大排,则最大的危险系数一定是最小的。
第七章 时空复杂度分析
一般ACM或者笔试题的时间限制是1秒或2秒
在这种情况下,C++ 代码中的操作次数控制在 $10^7$ 为最佳
下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:
- $n\le 30$ ,指数级别:dfs+剪枝,状态压缩dp
- $n\le 100\Longrightarrow O\left( n^3 \right)$ :floyd,dp
- $n\le 1000\Longrightarrow O\left( n^3 \right),O(n^2\text{log}n)$ :dp,二分
- $n\le 10000\Longrightarrow O\left( n\sqrt{n} \right)$ :块状链表
- $n\le 10^5\Longrightarrow O\left( n \text{log}n \right)$ :各种sort,线段树,树状数组,set/map,heap,dijkstra+heap,spfa,求凸包,求半平面交,二分
- $n\le 10^6\Longrightarrow O\left( n \right)$,以及常数比较小的 $O(n \text{log}n)$ 算法:
- hasp,双指针扫描,kmp,AC自动机
- 常数小:sort,树状数组,heap,dijkstra,spfa
- $n\le 10^7\Longrightarrow O\left( n \right)$ :双指针扫描,kmp,AC自动机,线性筛质数
- $n\le 10^9\Longrightarrow O\left( \sqrt{n} \right)$ :判断质数
- $n\le 10^{18}\Longrightarrow O\left( \log n \right)$ :最大公约数