贪心思想
一般用来解决“最优化”问题。总是从局部选取最“好”的结果，通过局部最优来推导全局最优。
贪心策略并不总是有解，也并不总是有最优解。因此全局最优解一般选用 动态规划 和其它 搜索策略
贪心可获得最优解的条件是问题具有 最优子结构性质，即每一步选择的最优解都是全局最优解中的一个解。
核心思路
找到一个 指标，对这一指标的贪心策略满足最优子结构性质。指标可以是题给的限制条件，也可以是另外构造的尺度。一般会使用 排序 预处理数据来辅助
经典问题思路
凑钱数：钱币面值由大到小选取
任务安排：结束时间从小到大选取
多机调度：执行时间从大到小选取
区间覆盖：选定区间一端，选定区间内从长到短选取
哈夫曼编码：节点从小到大选取
Dijkstra：子路径长度从小到大选取
实战应用
买苹果
只有小袋6个和大袋8个两种规格，问买N个苹果最少几袋。策略是尽可能拿大袋子，可将大袋从 $\scriptsize n / 8$ 开始倒序枚举。本题采用模运算直接假设全拿大袋，$\scriptsize 6$ 和 $\scriptsize 8$ 的数字组合对 $\scriptsize 8$ 取模结果为 $\scriptsize 0、2、4、6$
剩余 $\scriptsize 2$ 个时可用 $\scriptsize 6+6+6$ 替换 $\scriptsize 8\times 2+2$，此情况要求 $\scriptsize N \geqslant 18$。
剩余 $\scriptsize 4$ 个时可用 $\scriptsize 6+6$ 替换 $\scriptsize 8+4$，此情况要求 $\scriptsize N \geqslant 12$。
剩余 $\scriptsize 6$ 个时可用直接用小袋。
#include <iostream>
using namespace std;
int main() {
int N;
scanf("%d", &N);
if(N <= 5 || N == 10) {
printf("Cannot!");
return 0;
}
switch(N % 8) {
case 0: printf("%d", N / 8); break;
case 2:
case 4:
case 6: printf("%d", N / 8 + 1); break;
default: printf("Cannot!"); break;
}
return 0;
}
PAT-B1023 最小数
先选非零最小首位，再按数字由小到大输出
#include <iostream>
using namespace std;
int main() {
int s = 10, cnt[10];
for (int i = 0; i < 10; i++) {
scanf("%d", &cnt[i]);
if (i < s && i && cnt[i]) {
s = i;
cnt[i]--;
}
}
printf("%d", s);
for (int i = 0; i < 10; i++)
while (cnt[i]--)
printf("%d", i);
return 0;
}
PAT-A1070 最大利润
题意转为有限库存组合可获得的最大价格
贪心思想选定单价为指标，从大到小填充库存即可，直到填满结束
⊙_⊙ Q：库存还可以组合的？整懵了？
(∫・ω・)∫ A：从高单价到低单价依次扣除货品就好了。如果货品库存比剩余目标库存还多，当前货品就是最后一个，且为部分组合。如果剩余目标库存多，说明当前货品全要了。
∠(°ゝ°） Q：结构体数组排序一直报类型转换出错什么鬼？
(๑•̀д•́๑) A：自定义排序函数，入参是两个 结构体类型！一定要记住！
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1001;
struct obj {
double ivt;
double unit;
double total;
} o[maxn];
bool cmp(obj a, obj b) {
return a.unit > b.unit;
}
int main() {
int N;
double maxP = 0, D;
scanf("%d %lf", &N, &D);
for (int i = 0; i < N; i++)
scanf("%lf", &o[i].ivt);
for (int i = 0; i < N; i++) {
scanf("%lf", &o[i].total);
o[i].unit = o[i].total / o[i].ivt;
}
sort(o, o + N, cmp);
for (int i = 0; i < N && D; i++) {
int ivt = o[i].ivt;
if (ivt <= D) {
maxP += o[i].total;
D -= ivt;
}
else {
maxP += o[i].unit * D;
D = 0;
}
}
printf("%.2f", maxP);
return 0;
}
PAT-A1033 最小油价
总价最低，即目标是让高单价区间尽可能短，短单价区间尽可能长。每次选择最近的价格更低的油站，如果可达范围内没有价格更低的则选择可达站点中最低的一个
Q：我的策略是价格从低到高选取，每次选取最便宜且可达的油站，这样为什么不是最优？
A：你这个策略的效果是可达终点的所有方案中 单价和最低。打个比方：你是去十个班挑了成绩最好的学生，挑出的却不一定是年级前十。而我们的目标是 总价最低，不止有单价，还有距离的因素。如下例 $$\scriptsize U_{当前站} \rightarrow V_{价格介于U,V站} \rightarrow W_{下一价格最低站}$$ 要求当前站到下一最低价格站之间的价格也要最低，明显是需要走V的，而你的策略忽略掉了。
PAT A1037 最大乘积和
思路是取同号的两最大绝对值数乘积，即分别取排序后两个序列的两端，两端再依次向内收缩推进即可。
∠(+_+)? Q：我确实是按照本题思想实现的，只不过改用了一个大循环的双指针方法，先递增左侧，再递减右侧，用乘积大于0来判断加和，检测点2怎么就死活通不过呢？
（逃 ε=ε=ε=┏()┛ A：不要死磕过不去的样例，可以逐个将输入数据通过二分法猜出范围，猜对的范围输出一个错误答案，否则给他无限循环让提交出现超时，这样一定次数后就可确定出（读书人的事怎么能叫偷呢）准确样例（姥姥别打我！溜走…）。回到题上来，如果 两个都是正序列的话，应该从右向左，不能够从左向右吧！只有乘积>0是不够的，需要判断 两数同负再递增左，两数同正再递减右。同时不要忘记 指针不能越界。最后 不能把乘积=0划进来，如下样例，会导致索引为3时前后两个方向重复错误计算；实际上碰到0也没有必要加进来，不影响结果。
5 -1 0 2 3
3 -3 0 1
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100001;
int c[maxn], p[maxn];
int main() {
int nc, np;
scanf("%d", &nc);
for (int i = 0; i < nc; i++)
scanf("%lld", &c[i]);
scanf("%d", &np);
for (int i = 0; i < np; i++)
scanf("%lld", &p[i]);
sort(c, c + nc);
sort(p, p + np);
int lc = 0, hc = nc - 1;
int lp = 0, hp = np - 1;
long long maxR = 0;
while (lc < hc && lp < hp && c[lc] < 0 && p[lp] < 0) {
maxR += c[lc] * p[lp];
lc++;
lp++;
}
while (hc >= 0 && hp >= 0 && c[hc] > 0 && p[hp] > 0) {
maxR += c[hc] * p[hp];
hc--;
hp--;
}
printf("%lld", maxR);
return 0;
}
PAT-A1067 最小交换次数
Q：
A：0每交换回原位就多一次