贪心
贪心¶
基本概念¶
- 贪心算法的适用条件：要求问题具有贪心选择性质和最优子结构性质
- 贪心选择性质：整体最优解可以通过一系列局部最优的选择（贪心）达到
- 最优子结构性质：一个问题的最优解包含其子问题的最优解
- 贪心算法的操作要求：
- 符合问题要求
- 符合局部最优
- 执行后不能撤回
- 证明：
- 尝试证明贪心得到的解与最优解是相同的
例题¶
- P1080 NOIP2012 提高组] 国王游戏
- 很好的贪心排序思想，考虑相邻元素调换能不能使结果更优
- P5521 yLOI2019] 梅深不见冬
- 1.答疑 - 蓝桥云课 (lanqiao.cn)
- 排序问题，同样假设交换位置什么条件下可以使结果更优，从而获取排序条件
- 设 \(s_1a_1e_1s_2a_2e_2\)
- 若第一个人在前面耗时短即 \(2(s_1+a_1)+e_1+s_2+a_2 <= 2(s_2+a_2)+e_2+s_1+a_1\)
-
即 \(s_1+a_1+e_1<=s_2+a_2+e_2\)
中位数贪心¶
- （难）1703. 得到连续 K 个 1 的最少相邻交换次数
- 表达式分析比较复杂，使用前缀和加速
- 2448. 使数组相等的最小开销
- 加权