没错没错，这篇咕咕咕了十几天的文章，终于迎来了她的更新！！！
这个蒟蒻的学习路线特别奇怪呢，一会学那个一会学这个。
几天混了这么多分区的蒟蒻居然没有忘本
首先，我们需要知道，什么叫贪心。
贪心算法，也叫贪婪算法。贪心，顾名思义就是贪心地进行决策。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。
形象一点，就像是有一个贪婪的人，她每次选择的时候只顾眼前的优势，而不考虑将来的后果。 dy毒鸡汤：6
一个例子，假如现有 $1$ 分、$5$ 分、$25$ 分的硬币可用来找钱，现在我们需要找 $N=32$ 分的零钱，如何找？自然，我们先从面值大的来找：
首先找 $25$ 分钱，还剩 $7# 分钱。
自然，接下来我们找 $5$ 分钱，还剩 $2$ 分钱。
这 $2$ 分钱自然就只能用 $1$ 分的来找了。
于是到了最后，我们这32分就变成了1个25分、1个5分，以及2个1分了。
这是不得不提的一点：贪心，到底是不是正确的选择？
实际上，贪心决策的正确性是不能确定的，在这一个选硬币的例子中，确实是正确的。
但是这并不证明贪心就完全是对的，比如著名的01背包，这就需要用到DP了 本蒟蒻不会 qwq
背包的普遍题面是这样的：
有一个容量为 $V$ 的背包，还有 $n$ 个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积 $w$ 和价值 $v$ 。
问：如何向背包装物体才能使背包中物体的总价值最大？
看起来，我们可以直接使用贪心决策。
不过只要我们稍加验证，就发现我们不可以这么想，这是推倒贪心yyds的一个例子：
$V=10, n=4$
$w_1 = 8, v_1 = 9$ $w_2 = 3, v_2 = 3$ $w_3 = 4, v_3 = 4$ $w_4 = 3, v_4 = 3$
如果我们使用贪心的话，我们就应该选择性价比最高的物品：即$\frac{v}{w}$的值最大的的物品来放进背包。
显然，我们就可以优先拿第一个物品，因为$\frac{v_1}{w_1}=1.125$，而其余物品均为 $\frac{v}{w}=1$。
于是你拿了第一个东西，然后你会发现一个问题：这个背包装不下了！但是，其实它还有 $1$ 的空间。
So，贪心不能用的原因就是：它会出现浪费空间的现象，无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。
贪心，有着许多经典的例题：
有$N$堆纸牌，编号分别为 $1,2,…,N$。每堆上有若干张，但纸牌总数必为 $N$ 的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 $1$ 堆上取的纸牌，只能移到编号为 $2$ 的堆上；在编号为 $N$ 的堆上取的纸牌，只能移到编号为 $N-1$ 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 $N=4$ 时，$4$ 堆纸牌数分别为 $9,8,17,6$。
移动 $3$ 次可达到目的：
第一行共一个整数 $N$，表示纸牌堆数。
第二行共 $N$ 个整数 $A_1,A_2,\cdots,A_N$，表示每堆纸牌初始时的纸牌数。
共一行，即所有堆均达到相等时的最少移动次数。
4
9 8 17 63对于 $100%$ 的数据，$1 \le N \le 100$，$1 \le A_i \le 10000$。
【题目来源】
NOIP 2002 提高组第一题
这道题采用取平均数的方法，然后咕咕咕？！
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。