本文目录 ⌄
简单的说一下贪心算法及其运用
一.基本概念
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部的最优解。
举个例子来说就好比一条路上有两条路，一条路表面轻松，一条路表面艰难，但背后的路却谁也不知道，但这个算法永远都会选择那条轻松的路，而不管后面是怎么走的，简而言之目光短浅。但是目光短浅有的时候也可以求的最优解，这就要看问题本身了。
那么贪心算法在什么时候能够适用呢？
选择贪心算法的问题需要具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
在选择贪心算法的时候一定需要注意此性质，对于如何处理有后效性的题目，我们以后再做处理。
二.基本思路
1.建立数学模型来描述问题
2.把求解的问题分成若干个子问题
3.对每一个子问题求解，得到子问题的局部最优解
4.把子问题的解局部最优解合成原来解问题的一个解
三.适用问题
贪心算法只适用于从局部最优策略可以产生全局最优策略的题目，当然对于不满足的也可以使用，但不一定能适用！
对于贪心思路的正确性，一般来说都是不好去证明的，很多时候是靠自己感觉而来的。但是贪心思路的反例却比比较好找，找出反例便可以证明其错误性。
相信在阅读完上文的你应该大致了解了一下贪心算法把，接下来来看一道简单的例题，练练手吧！
四.例题
排队接水
有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。
这是一道非常简单的贪心题，很容易我们就可以知道，因为排队时，越靠近前面的时间计算的次数越多，因此越小的排在前面计算出来的结果就是最小的，所以这道题可以用贪心来进行解决。
（1）将时间从大到小进行排序
（2）将排序后的时间按顺序一次放入每个水龙头的队列中
（3）统计，输出答案
参考代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int t;
int num;
}a[1010];
int n;
double ans,sum;
bool cmp(node a,node b){
return a.t<b.t;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i].t);
a[i].num=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i){
printf("%d ",a[i].num);
sum+=(n-i)*a[i].t;
}
printf("\n");
ans=sum/n;
printf("%0.2lf",ans);
return 0;
} 另外放上几道练习题，有问题的可以评论或者QQ找我
P1031 均分纸牌 https://www.luogu.com.cn/problem/P1031
P1106 删数问题 https://www.luogu.com.cn/problem/P1106
P1020 导弹拦截 https://www.luogu.com.cn/problem/P1020
贪心比较重要的一点就是要多多练习，掌握一些基本的套路。
遇到问题如果不确定是否使用贪心算法，也可以大胆猜测，然后进行验证。