前言C算法与数据结构打开打包代码的方法兼述单元测试简介贪心算法Greedy Algorithm是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法策略。能通过贪心解决的问题往往有两个特性一贪心选择。二最优子问题即原问题的最优解可通过子问题的最优解合并得到。这个定义包含两层含义可以分解一个大规模的问题可以被分解成若干个规模更小的、相似的子问题。 最优传递通过组合这些子问题的最优解可以直接得到原问题的最优解。贪心算法的正确性必须证明。常见的证明方法有五种一反证法。二数学归纳法。三决策包容性。 四扩展决策范围。五临项交换。贪心举例力扣455. 分发饼干假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是满足尽可能多的孩子并输出这个最大数值。性质一如果某最优解至少让一个孩子满足但没有让胃口最小的小朋友x满足。则剥夺任意孩子的饼干给x仍然是最优解。小结一如果不能满足x则不能满足任意小朋友处理结束。如果能满足则满足x后对剩余小朋友和饼干继续迭代。性质二如果有多块饼干满足x则选择尺寸最小。y1y2xx1。某方案x选择y2x1选择y1。x 1 ≤ y 1 → x 1 y 2 x1 \le y1 \rightarrow x1 y2x1≤y1→x1y2,即交换x和x1也是最优解。实现分N步第n步选择胃口第n小的小朋友然后选择剩余饼干中≥ g [ n ] \ge g[n]≥g[n]且最小的饼干。1基础贪心从最小/最大开始贪心优先考虑最小/最大的数从小到大/从大到小贪心。在此基础上衍生出了反悔贪心。 从最左/最右开始贪心思考第一个数/最后一个数的贪心策略把 n 个数的原问题转换成 n−1 个数或更少的子问题。1.1最小(大)贪心如果答案与数组元素顺序无关一般需要排序。排序后可以遍历计算。【排序 贪心】3107. 使数组中位数等于 K 的最少操作数1604【C贪心】2567. 修改两个元素的最小分数1608【C 贪心 滑动窗口 前后缀分解】948. 令牌放置1762【C贪心】1262. 可被三整除的最大和1762【C贪心】1775. 通过最少操作次数使数组的和相等1850【C贪心 单调栈】1727. 重新排列后的最大子矩阵1926【C二分查找 贪心】1648. 销售价值减少的颜色球2050【C贪心 二分查找】2616. 最小化数对的最大差值2155【C贪心】1691. 堆叠长方体的最大高度2171【贪心 堆 优先队列】502. IPO无难度分【C贪心 二分查找】P6473 [NOI Online #2 入门组] 未了普及【C贪心】P7319 「PMOI-4」生成树普及【C贪心】P8782[蓝桥杯 2022 省 B] X 进制减法普及【C贪心】P8787 砍竹子普及【C贪心】P9050 [PA2021] Sumy普及【贪心二分双指针】P9559 [SDCPC2023] Fast and Fat普及【C贪心 树状数组】P8818 [CSP-S 2022] 策略游戏普及【贪心 大根堆】P9977 [USACO23DEC] Bovine Acrobatics普及【贪心 栈】P10849 [EGOI 2024] Bike Parking / 车位分配普及【贪心】P11112 [ROI 2024] 机器人物流 (Day 1)普及【树状数组 贪心】P11453 [USACO24DEC] Deforestation S普及【贪心 决策包容性】P12331 [蓝桥杯 2023 省 Java B] 最大开支普及【C贪心 滑动窗口】P7990 [USACO21DEC] Closest Cow Wins S省选-1.2反悔贪心反悔贪心是在贪心选择后保留撤销机制用堆等维护可反悔项后续若更优就替换先前决策修正局部最优兼顾效率与更优解。发现无法贪心时再更改。如完成第i个任务需要task[i]块砖头或一个梯子。问最多能完成多少个任务必须依次次完成任务。两种反悔贪心法一优先用砖头砖头不够就用梯子完成需要砖头最多的任务。二优先用梯子梯子不够。将需要砖头最少的梯子换成砖头。【反悔贪心 反悔堆】1642. 可以到达的最远建筑1962【大根堆】【反悔堆】【反悔贪心】【C算法】871 最低加油次数2074【反悔堆 反悔贪心】2813. 子序列最大优雅度2582【反悔贪心】【优先队列】3049. 标记所有下标的最早秒数 II3111洛谷难度等级【反悔贪心】P12187 [蓝桥杯 2025 省 Python A/Java A/研究生组] 原料采购普及【反悔贪心】P10051 [CCO 2022] Rainy Markets普及【C反悔贪心】P10051 [CCO2022] Rainy Markets普及【反悔贪心贪心 单调栈】P10334 [UESTCPC 2024] 饮料普及1.3单序列配对【C 贪心 双指针】2576. 求出最多标记下标|1843双序列配对【贪心算法】2071:你可以安排的最多任务数目|26481.4最左右贪心【C贪心】2522. 将字符串分割成值不超过 K 的子字符串1604【C贪心】2086. 喂食仓鼠的最小食物桶数1622【C贪心 位运算】2571. 将整数减少到零需要的最少操作数1649【C二分查找 贪心】792. 匹配子序列的单词数1695【C贪心】1536. 排布二进制网格的最少交换次数1880【C贪心 DFS】2673. 使二叉树所有路径值相等的最小代价1917【C贪心】2366. 将数组排序的最少替换次数2060【位运算 贪心】2835. 使子序列的和等于目标的最少操作次数2207【C贪心 决策包容性】3302. 字典序最小的合法序列2473洛谷题目难度【贪心】P8266 [USACO22OPEN] Photoshoot B普及【贪心】P4712 「生物」能量流动普及【C贪心】P8769 [蓝桥杯 2021 国 C] 巧克力普及【C贪心 二分查找】P8775 [蓝桥杯 2022 省 A] 青蛙过河普及2数学贪心基础【贪心】【二分查找】【动态规划】1739放置盒子|2198【C贪心】P6023 走路普及【贪心】P7076 [CSP-S2020] 动物园普及【C贪心】P9143 [THUPC 2023 初赛] 众数普及【C贪心】P9975 [USACO23DEC] Cowntact Tracing 2 B普及【C贪心 位运算】B3930 烹饪问题普及【C贪心】B4050挑战怪物普及【C贪心】P8087 『JROI-5』Interval普及【C贪心】P8792 [蓝桥杯 2022 国 A] 最大公约数普及【C贪心 数论】P8976 「DTOI-4」排列普及【贪心 单独栈】P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2普及【C贪心 前后缀分解】P9742 「KDOI-06-J」贡献系统普及【线性基 贪心】P4570 [BJWC2011] 元素省选-中位数贪心中值贪心是每步选当前数据的中位数作分割点或代表点使两侧规模尽量均衡降低最坏偏差实现简单、效率高但通常不保证全局最优。pos[0…n-1]升序记录了所有房间的位置将邮筒放在何处邮筒到各户的距离最短。结论如果n为偶数则pos[n/2-1]到pos[n/2]之间如果n为奇数pos[n/2]。下面用分组法和扩展决策范围来证明。先假定n是偶数分组法pos[i]和pos[n-1-i]一组任意一组最小距离为pos[n-1-i]-pos[i]放在两者的中间可以取最小值。当n 2时放在中间可以取最小值。当 n4,放置pos[1]和pos[2]中间可以取最小值。⋯ \cdots⋯放置到pos[n/2-1]和pos[n/2]可以取最小值。当n为奇数时邮箱放到pos[i]各组取最小值pos[i]为0。力扣难度分【C 同余 裴蜀定理 中位数贪心 并集查找】2607. 使子数组元素和相等2071【动态规划】【中位数贪心】【C算法】1478. 安排邮筒2190【贪心算法】【中位贪心】2968.执行操作使频率分数最大2444【动态规划】【前缀和】【中位数贪心】2463. 最小移动总距离2453【划分型dp 滑动窗口 中位数贪心 对顶堆】3505. 使 K 个子数组内元素相等的最少操作数2539【对顶队列】【中位数贪心】【前缀和】3086. 拾起 K 个 1 需要的最少行动次数2672洛谷难度等级【中位数贪心】 P11854 [CSP-J2022 山东] 宴会普及【中位数贪心】P6696 [BalticOI 2020] 图 (Day2)普及【中位数贪心 前缀和】P3819 松江 1843 路普及均值不等式周长为n的矩形最大面积是多少通俗的说算数平均值≥ \ge≥几何平均值当且仅当所有数相等时算术平均值等于几何平均值。完整的均值不等式调和平均数 ≤ 几何平均数 ≤ 算术平均数 ≤ 平方平均数 调和平均数\le 几何平均数 \le 算术平均数 \le 平方平均数调和平均数≤几何平均数≤算术平均数≤平方平均数【贪心 堆 】3081. 替换字符串中的问号使分数最小|1904【位运算 反证法 试填法 贪心 均值不等式】2897.对数组执行操作使平方和最大|2301排序不等式给定两个长度均为 n 的数组 a 和 b可以交换同一数组内的元素最小化/最大化∑ i : 0 N − 1 a [ i ] × b [ i ] \sum_{i:0}^{N-1}a[i]\times b[i]∑i:0N−1a[i]×b[i]把 a 和 b 都从小到大排序可以最大化上式。把 a 从小到大排序b 从大到小排序可以最小化上式。【 贪心 临项交换 多指针】2931. 购买物品的最大开销1822【C差分数组 贪心 排序不等式】1589. 所有排列中的最大和1871【C贪心】P6155 修改普及4决策包容性如果存在最优解增加某种条件限制后仍然有最优解。故只需要考虑此种条件下的最优解。【C二分查找 贪心 决策包容性】826. 安排工作以达到最大收益1708【C贪心 决策包容性】2498. 青蛙过河 II1759【C二分查找 贪心 决策包容性】2576. 求出最多标记下标1843【C二分查找 贪心】1552. 两球之间的磁力1919【C前缀和 动态规划 贪心】813. 最大平均值和的分组1936【C二分查找 贪心 决策包容性】1488. 避免洪水泛滥1973【贪心 决策包容性】2561. 重排水果2221【贪心 决策包容性 】757. 设置交集大小至少为23485 临项交换临项交换微扰证明在任意局面下任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。性质一a[i]和a[j]逆序j i 1则一定存在a[k]和a[k1]逆序否则a是顺序。【C贪心 临项交换】3219. 切蛋糕的最小总开销 II1789【C动态规划 贪心 临项交换】3180. 执行操作可获得的最大总奖励 I1848【C贪心 临项交换 】1665. 完成所有任务的最少初始能量1900【贪心 临项交换 博弈论】1686. 石子游戏 VI2000【C贪心 临项交换】3273. 对 Bob 造成的最少伤害2012【C贪心 临项交换 】2412. 完成所有交易的初始最少钱数2092【C贪心 临项交换 】2136. 全部开花的最早一天2033【C排序 贪心】910. 最小差值 II2134【反悔堆 优先队列 临项交换 决策包容性】630. 课程表 II无难度等级【贪心之临项交换】P8732 [蓝桥杯 2020 国 ABC]普及【贪心 临项交换】P8109 [Cnoi2021] 幻想乡程序设计大赛普及C贪心】P8411 「SvR-1」Problem普及【图论 拓扑排序 贪心 临项交换】P5603 小 C 与桌游 题解普及【C贪心 临项交换 前后缀分解】P6877 [JOI 2020 Final] 長いだけのネクタイ普及【C贪心 临项交换】P7095 [yLOI2020] 不离普及【贪心 动态规划】P8806 贪心之临项交换 动态规划普及【贪心 树状数组】P9310 [EGOI 2021] Luna likes Love / 卢娜爱磕 cp普及【贪心之临项交换 DFS 懒删除堆】P9369 [ICPC 2022 Xi‘an R] Tree普及【动态规划 贪心 临项交换】P9468 [EGOI 2023] Candy / 糖果普及【贪心之临项交换 二分查找 最大值最小化】P10190 [USACO24FEB] Target Practice II S普及排序【贪心冒泡排序回溯临项交换】P8719 [蓝桥杯 2020 省 AB2] 字串排序|普及6思维先特殊情况再一半情况。直接引用大佬的思维方式小型数组nums 只有 1 个数只有 2 个数只有 3 个数万里挑一nums 所有数都相同只有一个数不一样有两个数不一样某个数特别大二值化只有两种数例如 [0,1,0,1,0,1] 或者 ababab。反向思考如果答案是 1输入会是什么样的如果答案是 2是 nums[0]是 nums[1]枚举归纳试试小范围打表暴力枚举所有情况找规律。6.1 从特殊到一般【动态规划 数学】2745. 构造最长的新字符串|1607从特殊到一般【贪心】【分类讨论】2499. 让数组不相等的最小总代价|2633二值化【贪心 二分查找 树状数组 二值化】P10878 [JRKSJ R9] 在相思树下 III|普及6.2逆向思维及时间倒流主要两类一解决并集查找只能连接不能断开的缺点。二盖章之类可以多次操作以最后一次操作为准。【C贪心 数论 逆向思维】991. 坏了的计算器|1909【贪心 逆向思考 并集查找 数学归纳法】P7162 [COCI 2020/2021 #2] Sjekira普及7扩展决策范围放缩法在思考贪心算法时有时候不容易直接证明局部最优决策的正确性此时可以往后多扩展一步进而对当前的决策进行验证。扩展决策范围即往后多看一步。【C贪心 扩展决策范围 分治法】122. 买卖股票的最佳时机 II|中等难度28数学归纳法【C贪心 数学归纳法】1054. 距离相等的条形码|1701临项不同n个字符能否让相邻的字符不同。性质一出现次数最多的字符出现次数 n/2。则限制队首不为指定字符也可以让相邻不相等。性质二n是奇数。出现最多的条形码出现n/21次。如果队首可以为此条形码则可以让相邻不相等。下面用数学归纳法来证明。n为1成立{a}n为2成立{a,b},{b,a}n为3成立{a,b,a} {a,b,c}{a,c,b}从小到大证明n 4 To∞ \infty∞n为偶数如果存在两个众数为n/2将任意众数放到队首余下的符合性质二。否则将任意众数放到队首余下的符合性质一。n为奇数如果众数为n/21则只有一个众数。否则两个众数的数量为n1与n个数矛盾。将众数放到队首余下的符合性质一。从上面的证明过程得知如果有解则将众数放到最前面一定存在解。【C贪心 数学归纳法】1054. 距离相等的条形码1701【C二分查找 贪心】2856. 删除数对后的最小数组长度1749【C贪心】1953. 你可以工作的最大周数1803子分类区间贪心最多不相交区间、区间选点、区间合并、区间覆盖、区间分组字符串贪心其它【C贪心】2712. 使所有字符相等的最小成本1791【C贪心 分治】1717. 删除子字符串的最大得分1867【C前缀和 位运算 贪心 】2680. 最大或值1912【C前缀和 数论 贪心】2245. 转角路径的乘积中最多能有几个尾随零2036【贪心】【回溯】【字符串】2014. 重复 K 次的最长子序列2558【C算法 折线图 贪心】135分发糖果分数未知【贪心]【字符串】【分类讨论】420 强密码检验器无难度分洛谷题目难度等级【C贪心 二分查找 寻找尾端】P8161 [JOI 2022 Final] 自学 (Self Study)普及【C贪心】P8800 [蓝桥杯 2022 国 B] 卡牌普及【C 区间贪心】P9344 去年天气旧亭台普及【C贪心】P9228 原神普及【C贪心】P9728 [EC Final 2022] Dining Professors普及【贪心 排序】P10072 [GDKOI2024 普及组] 刷野 I普及【C贪心 图论】P10166 [DTCPC 2024] 环普及【C贪心】P11044 [蓝桥杯 2024 省 Java B] 食堂普及【C贪心 前后缀分解 滑动窗口】P6878 [JOI 2020 Final] JJOOII 2普及【贪心】P7301 [USACO21JAN] Spaced Out S普及【贪心】P8188 [USACO22FEB] Email Filing S普及【C贪心】P8896 DPOI-1」道路规划普及【C贪心 BFS】P8977 「DTOI-4」行走普及【剪枝 贪心 回溯】B4093 [CSP-X2021 山东] 发送快递普及【模拟 贪心 双指针】B4207 [常州市赛 2021] 战士普及【C贪心】P9965 [THUPC 2024 初赛] 转化省选-【C贪心 前后缀分解】P9128 [USACO23FEB] Fertilizing Pastures G省选未分类2024年10月24整理)扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。
