《算法》读书笔记
2021-08-04 16:00:43 0 举报
AI智能生成
最值问题是算法中的一种常见问题,其解法通常包括暴力搜索、分治法、动态规划等。暴力搜索是最简单也是最直接的方法,通过穷举所有可能的情况来找到最值。分治法则是将问题分解为若干个规模较小的子问题,递归求解子问题的最值,再将子问题的解合并得到原问题的解。动态规划则是通过将问题划分为若干个子问题,并记录每个子问题的最优解,从而避免重复计算,提高求解效率。这些方法各有优缺点,适用于不同类型的最值问题。
作者其他创作
大纲/内容
最倒霉+1(抽屉原理)
特征
至少(最少)......保证;
方法
找出最倒霉的情况并+1
反向结构
集合结构
特征
都......至少
方法
反向
总数减去每一个主体
加和
将减出来的数字加和
做差
总数减去第二步加出来的和
数列
特征
最...最...;排名第...最...;
方法
排序
看题目是问最大最小还是第几名
定位
找到所求的量,并将其设为x
加和
列方程,等式左边是所有的量都加在一起,等式右边是总量
等式左边的式子记得用等差公式
首项加末项乘以项数除以2
中位数乘以个数
筛选
至多选小,至少选大
类型
各不相同
1、最多的至少有几个
x+x-1+x-2+...+x-n=总数
2、最少的至多有几个
x+x+1+x+2+...x+n=总数
3、排名第n,最多的至少有几个?
n左边跟2相同,n右边是1+2+...
x+x-1+...+n+...+2+1=总数
4、每人最多n个,某人最少至多
n+n-1+...+x=总数
5、最多的最多
1+2+3+...+n+x=总数
可以相同
6、最多至少
x+n(x-1)=总数
7、最多的最多
n+x=总数
与其他题型相结合
能结合的题型
容斥原理
不定方程
经济利润
选票模型
最倒霉+1
方法
利用最值的逆向思维
用每个部分自己的方法
0 条评论
下一页