主要思想
贪心算法的思想主要可以概括为“总是做出当前看起来最优的选择”，也就是不从整体上进行考虑，所得到的答案是某种意义上的局部最优解，不一定是整体最优解。
贪心算法没有固定算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
贪心算法一般用于得到某些问题的“最优解”，一般来说具体表现为，求解某种最大值或者最小值(因为贪心一定是以某种策略选择局部最优，所以不会得到所有解的情况)
适用场景
1. 贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2. 最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。
基本解题思路
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
tips.在贪心算法中，很多时候需要数据具有有序性(因为这样你才能按照顺序去考虑所谓的"最优")
例题
1.排队打水
这个题可以类比为现实生活中，在超市购物时，在你前方排队的人拿着一车的商品，而你只想买一瓶可乐，那么如果你先结账，他只需等待几秒，如果他先结账，那么你将会等待几分钟那么我们可以得知，对于局部而言，有 “结账时间短的优先结账可以节约时间” 的初步结论，并且显而易见，商品越少的人越早结账，就会越节约所有人的整体时间，可以由此推出整体结论。
那么代码逻辑就很清晰了，如果打水时间短的需要在前面，我们就需要对他们进行排序
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL ans;
int a[N];
int main()
{
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
sort(a,a+n);
for(int i=0;i<n;i++)
{
ans += a[i] * (n-i-1);
}
cout << ans;
return 0;
}2.货仓选址
看到这个题目，思考一下在初中时是不是有这样一种几何题：
当一个点在何处时， 使得他与另外两个点 a,b 的距离之和最小
答案： 在a,b两点连成的线段上
那么本题已经保证了都在同一条数轴上，但是点由a,b两个变成了更多，那么我们将这个问题转化成一个几何问题的模型：当一个点在何处时， 使得他与另外n个点的距离之和最小
答案不难思考便可得出，在中间点上（n为奇数）或中间两点的线段上（n为偶数），据此我们可以写出完整代码，如下。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int n,ans;
int main()
{
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
sort(a,a+n);
for(int i=0;i<n;i++) ans += abs(a[n>>1] - a[i]);
cout << ans;
return 0;
}3.huffman
哈夫曼树其实也是基于贪心来构建的一种特殊二叉树，其主要构建方法就是每次将序列中最小的两个结点合并，得到新的父节点并加入回序列，直到序列完全变成一个二叉树结构
分析题意可以得知我们需要不断合并两堆果子，并且每次合并的消耗是两堆果子的数量，那么如果消耗要尽量小，我们需要尽量避免大堆的果子的合并，这跟哈夫曼树的构建过程不约而同，在本题中，我们不需要用到哈夫曼编码，所以我们可以借用小根堆来模拟哈夫曼树的构建过程，代码表示如下：
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
priority_queue<int,vector<int>,greater<int>> a;
int n;
long long ans;
int main()
{
cin >> n;
for(int i = 0;i<n;i++){
int x;
cin >> x;
a.push(x);
}
while(a.size() > 1){
int x = a.top();
a.pop();
int y = a.top();
a.pop();
a.push(x+y);
ans += (x+y);
}
cout << ans;
return 0;
}练习题
光靠以上几个题目对贪心只是做一个入门了解，多刷题才能更深入透彻的理解贪心算法，以下是几个练习题目，可以闲时做着玩玩。
