贪心$(Greedy$ $Algorithm)$的定义

贪心是一种在每一步选择中都采取当前状态下最优(局部最优)的决策，从而希望导致全局最优解的算法策略
它不回溯或重新考虑之前的决策，因此效率较高，但并非所有问题都适用

特点

• 局部最优选择：每一步只考虑当前最优解，不依赖未来的选择
• 无后效性：当前决策不会影响后续决策的可行性
• 高效性：通常时间复杂度较低，但需要验证问题的贪心性质

适用场景

贪心算法适用于具有贪心选择性质和最优子结构的问题，例如：

• 最小生成树$(Prim/Kruskal算法)$
• 最短路径问题$(Dijkstra算法)$
• 活动选择问题选择不重叠的活动的最大集合
• 霍夫曼编码构造最优前缀码

贪心的局限性

• 不保证全局最优：局部最优的累积可能无法得到全局最优解(如部分背包问题需用动态规划)
• 依赖问题性质：需证明贪心选择的正确性，例如通过数学归纳法或反证法

贪心与动态规划的区别

• 贪心：无回溯，仅依赖当前最优选择
• 动态规划：保存子问题解，通过状态转移逐步求解

正确性验证
贪心算法的正确性通常需通过以下方式证明：

1. 贪心选择性质：每一步的局部最优解能构成全局最优解。
2. 最优子结构：问题的最优解包含子问题的最优解。

例如，活动选择问题中，每次选择结束时间最早的活动，可以确保剩余时间最大化。

贪心模板

这个不好讲，结合例题直接给了，分析部分会更长点

贪心例题展示

$题目传送门$

P5019 [NOIP 2018 提高组] 铺设道路

题目背景

NOIP2018 提高组 D1T1

题目描述

春春是一名道路工程师，负责铺设一条长度为 $n$ 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 $n$ 块首尾相连的区域，一开始，第 $i$ 块区域下陷的深度为 $d_i$ 。

春春每天可以选择一段连续区间 $[L,R]$ ，填充这段区间中的每块区域，让其下陷深度减少 $1$。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 $0$ 。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 $0$ 。

输入格式

输入文件包含两行，第一行包含一个整数 $n$，表示道路的长度。 第二行包含 $n$ 个整数，相邻两数间用一个空格隔开，第 $i$ 个整数为 $d_i$ 。

输出格式

输出文件仅包含一个整数，即最少需要多少天才能完成任务。

输入输出样例 #1

输入 #1

6   
4 3 2 5 3 5

输出 #1

9

说明/提示

【样例解释】

一种可行的最佳方案是，依次选择：
$[1,6]$、$[1,6]$、$[1,2]$、$[1,1]$、$[4,6]$、$[4,4]$、$[4,4]$、$[6,6]$、$[6,6]$。

【数据规模与约定】

对于 $30\%$ 的数据，$1\le n\le 10$ ；
对于 $70\%$ 的数据，$1\le n\le 1000$ ；
对于 $100\%$ 的数据，$1\le n\le 100000,0\le d_i\le 10000$ 。

分析

为么贪
分析一下题目，直接看要求
要填路，且有不同深度(可能为0)
让你一天选择区间【$L,R$】进行填充
每次填充深度【$1$】
询问最优解是几天
看起来很像贪心
实际上就是贪心
如果用别的算法计算会比较难
这时候就要考虑贪心
实际上是因为题目标签就是贪心
怎么贪
想想思路~
找到一个突破点：如果两个点都是坑可以一起填
意思就是说如果你要填这个坑，并且旁边有个比$Ta$小的坑
这时候这个较小的坑就可以跟较大的坑一起填
$还没听懂的看这里$：
如果填坑$a[n]$,深度$=x$
且$a[n-1]$,但是其深度$\le x$
那么在此基础上可以用同样的时间填更多的坑
这就是这道题的贪心思路
核心部分代码实现

if(a[i]>a[i-1]){
	sum+=a[i]-a[i-1];
}

注意从$a[2]$开始，总和加上$a[1]$！

整体部分代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
//记得开long long
int a[114514];
signed main(){
    int n,day;
	cin>>n;
	for(int i=1;i<=n;i++)
        cin>>a[i];
    day=a[1];
	for(int i=2;i<=n;i++)
        if(a[i]>a[i-1])day+=a[i]-a[i-1];
	cout <<day;
	return 0;
}

题单推荐

$贪心题单$
例题和题单来自$洛谷$

~ $完结撒花$ ~

附：昨天写完了但是因为某些原因今早才发
之前漏了很多，把基础补回来之后再讲后面的例题
推荐$洛谷$作为你的刷题区域
下一篇预告：还在找例题~