读前声明：作者markdown和文笔一样差
制作不易，给个赞吧~
贪心，和其他算法。。。不对，贪心其实是一种思想。
虽然但是为什么大家都叫他算法啊（
贪心和大部分算法不一样，他要证明！
证明这种方法是对的！
我好讨厌证明啊啊啊，但是必须要啊啊啊啊
不证明？WA慢走不谢！如臭名昭著的石子合并，看着贪心，其实是个DP
咋证明？可以用反证法、构造法、调整法和其他一堆，但是还是这三个常用。
其中反证法和调整法又最常用。
一个个来。
反证法
思路就是用贪心的策略，依次构造出一个解 \(S1\)，假设最优解 \(S2\) 不同于 \(S1\)，可以证明是矛盾的，从而得出 \(S1\) 就是最优解。
例题：
最大整数
【问题描述】
设有 \(n\)（\(n\)≤20）个正整数（小于或等于 \(2147483647\)），将它们连接成一排，组成一个最大的多位整数。例如 \(n\)=\(3\)，\(3\) 个整数为 \(13\)、\(312\) 和 \(343\)，连接成的最大整数为 \(34331213\)。
【输入格式】
第 1 行 1 个整数 \(n\)。
第 2 行为 \(n\) 个正整数，每两个数之间用一个空格隔开。
【输出格式】
一行一个数，表示连接成的最大整数。
【输入样例】
4
7 13 4 246
【输出样例】
7424613
思路
首先想到大的字符串在前。
因为一般情况下 \(a>b\)（\(a\)，\(b\) 都是字符串），那么 \(a+b>b+a\)
但是！比如
\[a=121,b=12 \]\[a+b=12112 \]\[b+a=12121 \]明显 \(a+b<b+a\)
那咋办？
欸你看到我几次提到 \(a+b,b+a\) 了吗？
那我们可以用 \(a+b\) 和 \(b+a\) 比较啊！
苏！
到了证明！
引理：
记 \(nA\) 为 \(n\) 个字符串 \(A\) 按字符串加法运算规则相加之和，则由 \(A+B≥B+A\) 可推导出 \(nA+mB≥mB+nA\)，其中 \(m\)，\(n\) 为任意的自然数。用反证法可证明反过来也成立。
所以，设 \(la\) 为字符串 \(A\) 的长度，\(lb\) 为字符串 \(B\) 的长度，\(lc\) 为字符串 \(C\) 的长度，再设 \(n=lb*lc\)，\(m=la*lc\)，\(k=la*lb\)，则 \(nA\)，\(mB\)，\(kC\) 三 个 字 符 串 等 长，根 据 引 理 有：\(nA+mB≥mB+nA\)，\(mB+kC≥kC+mB\)，从而得到 \(nA≥mB≥kC\)，所以 \(nA+kC≥kC+nA\)，\(A+C≥C+A\)。
所以，要使 \(n\) 个字符串拼接起来后得到一个最大的字符串和式，则一定要将按上述定义最大的字符串放在第一个，否则必可通过将最大的字符串与它左侧的字符串交换得到更大的字符串和式。
调整法
就是用贪心的策略，依次构造出一个解 \(S1\)。假设最优解 \(S2\) 不同于 \(S1\)，找出不同之处，在不破坏最优性的前提下，逐步调整 \(S2\)，最终使其变为 \(S1\)，从而 \(S1\) 也是最优解。
没错这很生涩，还是来道题！
没错！这道题和大湾区T3很像！
例题：
问题描述：
一天，晨晨发现自己的 \(n\)（\(2<=n<=100\)）只兔子跑到自己的花园里面，它们在尽情的吃着她的宝贝花卉。晨晨看在眼里痛在心里，她现在只能把兔子逐个的抓回笼子里面。而送每只兔子回去的时间都不同，例如送第 \(i\) 只兔子回去需要 \(ti\)(\(1<=ti<=100\))单位时间，那么晨晨送第 \(i\) 只兔子总共需要花费 \(2*ti\) 单位时间，另外每一只兔子单位时间的破坏力都不同，例如第 \(i\) 只兔子单位时间内破坏 \(di\)(\(1<=di<=100\))朵花。
现在的问题是，晨晨如何安排送这 \(n\) 只兔子回笼子才能使这些兔子的破坏最小。
输入格式：
第一行：一个整数 \(n\)(\(1<=n<=100\))；
接着有 \(n\) 行，每行两个空格分开的整数 \(ti,di\),分别代表每一只兔子的送回去的时间，和单位时间破坏力。
输出格式：
一行：一个整数，代表这些兔子破坏多少花卉。
输入样例：
6
3 1
2 5
2 3
3 2
4 1
1 6
输出样例：
86
思路
水题。
排个序。
用sort。
重点在cmp函数！
首先不管是只对 \(ti\) 还是只对 \(di\) 排序都会被无情的
H A C K
！
那怎么办？
我们cmp对橙色兔子和蓝色兔子排序，红色部分不管。
记得当时讲大湾区T3时，不著名用户@TallBanana 问我为什么红色不管。
左边在你后边，不关你事；
右边在你前面，不管你在前在后都要吃那堆花。
那比较谁在前吃的少不就好了？
但是只会这些，你还是太弱乐！
一些难题
蜈蚣
贪心最多倒霉到什么程度。
有点坑，要把所有凑不齐一双的拿了，然后坑害强迫症把每一种袜子都拿一双少一个，最后把少的那个拿了。
[JSOI2007]建筑抢修
贪心好助手——优先队列！
点开链接是我写的优先队列学习笔记。
潜水比赛
sort完处理，有点难想。
鞋盒（box）
和蜈蚣差不多。
后记
贪心很实用。
不管是OI还是现实，第一直觉就是贪心。
虽然石子合并是DP，你在第一直觉不就是贪心？
谁会先推DP啊。
我的易错点
喜欢用cincout。
你好TLE。
想错。
我太弱了，总是想错（应该要列草稿才行吧）。
不证明。
我很懒，不证明，所以老是白费时间写错误代码。
想复杂。
一道sort+cmp我能写出猪国杀还长的代码。
学习贪心+写贪心题的感受
累人。
种类太多了。
学习贪心听课就行，很简单；
写题。。。额。。。噩梦啊。。。
就是要多想贪心方法，然后证明他，然后写的简单一点。
虽然但是这不应该很简单嘛。
但就是很难。
我觉得在于多练。
写给未来的自己：
给 我 多 刷 贪 心 题 ！
多练，熟能生巧。
彩蛋
没错还是我们的@TallBanana。
他说：“所有算法都是贪心！”
我：“？？？？？？”
他：“为了贪心的拿到更多分，所以使用这些算法！”
我：“IEE”
一些不方便在正文说的东西
Q：为什么我的题不按照什么“最值”什么的分？
A：我不是很认同这么分题目。
这样会锁住你的思维，看到题后不是先想怎么做，而是先想是什么类型，才想怎么做。
而且同一个类型题目千变万化。
Q：为什么最后“一些难题”那里很少？
A：学校网站的题。
写在最后
贪心真的又难又简单。
需要很多练习才可能掌握。
啊啊啊为什么我那么弱，贪心都不会啊啊啊！！！