最值问题的信号
2026-09-06 17:24:41
发布于:上海
最值问题
最值问题的信号
贪心信号
关键词:“最多”“最少”“最小”
特征:排序后有单调性,每步选择只看当前状态,各元素之间独立或独立或只有简单约束。
时间复杂度:O(nlogn),N<=1e6,时间开销主要在排序上。
DP信号
关键词:“最大价值”“最小奶牛数”“那到达的最高音量”“恰好”“方案数“。
特征:有约束导致选择冲突,一个选择会影响另一个选项的可行性。
时间复杂度:O(nm),N,M<=1e4/1e3
2分信号
关键词:“最大值最小”“最小值最大”
特征:给一个最值定义,求这个最值定义的最大化/最小化。
时间复杂度:O(nlogn),logn:2分,n:循环
这里空空如也





















有帮助,赞一个