贪心算法

 int a[1000], b=5, c=8;
 swap(b, c);    // 交换操作
 memset(a, 0, sizeof(a)); // 初始化为0或-1

引导问题

为一个小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆，第i个房间有J[i] 磅的五香豆，并且需要用F[i]磅的猫粮去交换；求老鼠最多可换多少豆？若五香豆不能全换猫粮，按比例换。

Sample Input 
  5 3 ——M猫粮   N房间
  7 2 ——五香豆  猫粮
  4 3
  5 2
  -1 -1 —— 结束

Sample Output
  13.333

由按比例换，7/2=3.5  4/3=1.333...  5/2=2.5  3.5最大 排序，一次换——7+5+1.3333=13.333

---

初识贪心

在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体上加以考虑，所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。

---

例题

1.田忌赛马

每个马跟比自己弱的程度最小的马

1.排序

2.蓝色最大和红色最大比较，看蓝色能不能比过红色，若比不过，拿蓝色最小的跟红色比

3.拿蓝色最大跟红色第二大的比...能比就比，不能就继续拿最差的跟最好的比

---

反证法上大分~事件序列问题

已知N个事件的发生时刻和结束时刻。

一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。

事件序列包含的事件数目，称为该事件序列的长度。

请编程找出一个最长的事件序列。

至少存在一个最长事件序列包含最早结束事件（最早结束事件是0）

反证法证明上句：

假设所有最长事件序列都不包含最早结束事件；只要证明这个假设是错的，原命题得证；

任取一个所谓的最长事件序列，把第一个事件去掉，换掉事件0，肯定跟后面都不冲突（因为换上的是最早结束的时间，原来都不冲突，现在更不冲突）

证明完后选中最早结束事件0   后面我做类似的：每次找一个最早结束的事件，只要和前面的不冲突的都选中；

---

2.搬桌子

一个公司要做调整搬桌子，房间有400个，一边是单号，一边双号；

走廊很窄，只通过1个桌子过；

输入：

第二行：趟数

第三行：房间号：10号搬到20号

每趟搬要10min：不重叠可以同时搬，要10min；重叠要分开搬

法一：与上题的思想差不多，只不过，改成了最早开始事件（找开始最早的）

法二：统计每个区间在时间轴上的重叠次数，并找出最大重叠次数的区间。

#include <bits/stdc++.h>
using namespace std;int main() {int t, i, j, N, P[200];  // t是测试用例的数量，N是每个测试用例的区间数量int s, d, temp, k, MAX;  // s和d是区间的起点和终点，MAX用于记录最大重叠次数cin >> t;for (i = 0; i < t; i++) {// 初始化P数组，用于记录每个时间点的重叠次数for (j = 0; j < 200; j++)P[j] = 0;cin >> N;  // 读取当前测试用例的区间数量for (j = 0; j < N; j++) {cin >> s >> d;  // 读取区间的起点和终点s = (s - 1) / 2;  // 将起点转换为数组索引d = (d - 1) / 2;  // 将终点转换为数组索引// 如果起点大于终点，交换它们if (s > d) {temp = s;s = d;d = temp;}// 在区间[s, d]内的每个时间点增加计数for (k = s; k <= d; k++)P[k]++;}// 找到最大重叠次数MAX = -1;for (j = 0; j < 200; j++)if (P[j] > MAX)MAX = P[j];// 输出最大重叠次数乘以10cout << MAX * 10 << endl;}return 0;
}

---

3.删数问题

已知一个长度不超过240位的正整数n（其中不含有效字0），去掉其中任意s（s小于n的长度）个数字后，将剩下的数字按原来的左右次序组成一个新的正整数。

给定n和s，请编程输出最小的新正整数。

Sample Input
178543 4
Sample Output
13

法一：从左到右扫描逆序对，删掉左边的数，若没有逆序对，删掉最后一位数

1 7 8 5 4 3 —— 1 7 5 4 3 ——1 5 4 3 ——1 4 3 —— 1 3 

1 2 3 4 

---

4.青蛙的邻居

每个湖泊都有一个青蛙，如果两个湖泊之间有水渠相连，我们认为两个青蛙他们为邻居；

问：你可以画出这个湖泊分布图吗？

Sample Input

3

7 —— 青蛙个数

4 3 1 5 4 2 1 —— 第一个青蛙有4个邻居；第二个青蛙有3个邻居....

6

4 3 1 4 2 0

6

2 3 1 1 2 1 

Sample Output

YES

NO

YES

 用以下知识可解决：

---

离散数学：可图性判定 

两个概念：

1.度序列：若把图A所有顶点的度数排成一个序列S，则称S为图A的度序列。

度：一个顶点他有几条边，度就是几

图A

2 3 1 1 1 就是度序列

2.序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。

若度序列2 3 1 1 1可以画出图A，就是可图的；

---

Havel-Hakimi定理：解决可读性判定

之后再排序：3 2 2 2 1

做一趟，排序一次；只要出现负数，就不可能了，图画不出来；最后全变成0，可以画；

Havel定理的解释——加加减减与图的对应关系_哔哩哔哩_bilibili

---

特别说明

若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！

在使用贪心算法解决问题时，必须首先证明贪心策略能够导致整体最优解。贪心算法通常通过每一步选择局部最优解来构建全局解，但并非所有问题都适合使用贪心算法，因此证明其正确性是关键。

说明理由：

若某货币系统有三种币值，分别为一角、五分和一分；要找1角5分
求最小找币数时，是否可以用贪心法求解？

可以；先用最大的能找几个找几个；

如果将这三种币值改为一种一分、五分和一分；要找1角5分

是否还可以使用贪心法求解？

不行；

因为他不成倍数；

贪心算法的常见操作：

贪心总是要找最大的、最小的、最划算的，往往要排序；