# 贪心

while 能朝给定总目标前进一步 do
求出可行解的一个解元素；由所有解元素组合成问题的一个可行解

## 算法思路

1. 建立数学模型来描述问题。要确定优化测度

2. 把求解的问题分成若干个子问题（集合划分）。是迭代划分的。

3. 对每个子问题求解，得到子问题的局部最优解

4. 把子问题的解局部最优解合成原来解问题的一个解。

## 算法特性

1. 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。

2. 随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象

3. 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

4. 还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

5. 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

6. 最后，目标函数给出解的值。常用技巧：排序、维护最优解

1.微扰(邻项交换)

2.范围缩放

3.决策包容性

4.反证法

5.数学归纳法

6.调整法

### 时间复杂度

$10^5$ $O(nlogn)$ 排序

$106-107$ $O(n)$ 扫一遍，往往需要推公式等直接求

$1000$ $O(n^2)$ 两重循环

## 区间问题

### 1. AcWing 905. 区间选点

1. 将每个区间按照右端点从小到大排序

2. 从后往前依次枚举每个区间 #### sort()函数自定义排序

sort() 函数有 2 种用法，其语法格式分别为：

• 升序：sort(begin,end,less())

• 降序：sort(begin,end,greater())

### 2. AcWing 908. 最大不相交区间数量

1. 将每个区间按照右端点从小到大进行排序

2. 初始时，用ed表示当前放置在数轴上的点的位置，开始初始化为无穷小，表示没有放置，此时数轴上没有点

3. 依次枚举排序好的每个区间。如果区间的左端点大于当前放置点的位置，说明当前点无法覆盖区间，则把点的位置更新成该区间的右端点，表示在该区间的右端点放置一个新的点，同时更新点的个数

### 3. AcWing 906. 区间分组

1. 对区间按左端点由小到大排队，在前优先入组

2. 记录每个小组的最大右端点作为入组标准，并且要维护所有小组中最小的最大右端点

3. 将候选集合中左端点最小的区间加入到最大右端点最小的小组 #### C++优先队列

priority_queue与queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

• top() 访问队头元素

• pop() 弹出队头元素

• empty() 队列是否为空

• size() 返回队列内元素个数

• push() 插入元素到队尾 (并排序)

• emplace() 原地构造一个元素并插入队列

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

1. 使用负数

2. priority_queue<int , vector, greater> heap

#### Python

##### Python优先队列

heapq 库是Python标准库之一，提供了构建小顶堆的方法和一些对小顶堆的基本操作方法(如入堆，出堆等)，可以用于实现堆排序算法。

1. 大顶堆：每个节点(叶节点除外)的值都大于等于其子节点的值，根节点的值是所有节点中最大的。

2. 小顶堆：每个节点(叶节点除外)的值都小于等于其子节点的值，根节点的值是所有节点中最小的。

heapq中创建堆的方法有两种。

heappush(heap, num)，先创建一个空堆，然后将数据一个一个地添加到堆中。每添加一个数据后，heap都满足小顶堆的特性。

heapify(array)，直接将数据列表调整成一个小顶堆(调整的原理参考上面堆排序的文章，heapq库已经实现了)。 heappop(heap)，将堆顶的数据出堆，并将堆中剩余的数据构造成新的小顶堆。

nlargest(num, heap)，从堆中取出num个数据，从最大的数据开始取，返回结果是一个列表(即使只取一个数据)。如果num大于等于堆中的数据数量，则从大到小取出堆中的所有数据，不会报错，相当于实现了降序排序。

nsmallest(num, heap)，从堆中取出num个数据，从最小的数据开始取，返回结果是一个列表。

merge(list1, list2)，将两个有序的列表合并成一个新的有序列表，返回结果是一个迭代器。这个方法可以用于归并排序

heappushpop(heap, num)，先将num添加到堆中，然后将堆顶的数据出堆。

heapreplace(heap, num)，先将堆顶的数据出堆，然后将num添加到堆中。

### 4. AcWing 907. 区间覆盖 ### 7. AcWing 112. 雷达设备

#### 逆向思维 ## Huffman树

### 构造过程

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

### 构建哈弗曼树的算法实现

• 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；

• 如果介于两个结点权重值之间，替换原来较大的结点；

### 1. AcWing 148. 合并果子 ## 排序不等式

$$\sum\limitsn_{i=1}a_ib_{n+1-i}\leq\sum\limitsn_{i=1}a_ic_i\leq\sum\limits^n_{i=1}a_ib_i$$ ### 1. AcWing 913. 排队打水

$$s_i = t_1 + t_2 + t_3 + \cdots + t_{i-1}$$
$$sum = \sum\limits_{i} s_i$$

$$sum = t_1 * (n-1) + t_2 * (n-2) + \cdots + t_{n-1} * 1 + t_n * 0$$

## 绝对值不等式

$| a |$表示数轴上的点a与原点的距离叫做数a的绝对值

$$||a| - |b|| ≤ |a+b| ≤ |a|+|b|$$

1、当a，b同号时它们位于原点的同一边，此时a与﹣b的距离等于它们到原点的距离之和。
2、当a，b异号时它们分别位于原点的两边，此时a与﹣b的距离小于它们到原点的距离之和。(|a-b|表示a-b与原点的距离，也表示a与b之间的距离)
$$|b - a|\leq|a - x| + |b - x|$$

$|a - x| + |b - x|$几何意义是x到a, b两点距离之和

### 1. AcWing 104. 货仓选址 ## 推公式

### 1. AcWing 125. 耍杂技的牛 - AcWing

#### C++ pair

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。

pair的实现是一个结构体，主要的两个成员变量是first和second。因为是使用struct不是class，所以可以直接使用pair的成员变量。

• 这一对值可以具有不同的数据类型（T1和T2），

• 两个值可以分别用pair的两个公有函数first和second访问。

### 3. AcWing 1536. 均分纸牌

#### 考虑 “纸牌均分问题” 如何解决？

$$\sum_{i=1}{n−1}|\sum_{j=1}i(cj−TM)|$$

$$\sum_{i=1}{n−1}|\sum_{j=1}i A_j|=\sum_{i=1}^{n−1}|S_i|，其中 S_i 为 A_i 的前缀和，即 S_i=\sum_{j=1}^iA_j$$

### 4. AcWing 122. 糖果传递

$$Min =\sum\limits^n_{i=1}|C[i]|$$

#### 思路一：前缀和 + 贪心

##### 考虑 “纸牌均分问题” 如何延伸到 “环形纸牌均分问题” ？

1. 出现一个环这种方案肯定不是最优解，因为给出去的纸牌经过一圈收回来了，显然浪费了操作次数我们在这个环上断开交易数量最小的一条交换边，并使其他边减少该边的交换数量，必然不会使方案变差
2. 出现一个点到达另一个点有两条路径我们可以断开起点两条出边中 val=cnt×wval=cnt×w 最小的那一套边，并该边权值累加到另一条路径的每一条边上，其结果不会变差（其中 cntcnt 是起点到终点路径上经过的点数，ww 是这条边的权重）

$$∑_{i=1}^n|S_i−S_k|，其中 S_i 为 A_i 的前缀和，即 S_i=∑_{j=1}^iA_j$$

$$\sum_{i=1}^{n-1} \Big| { \sum_{j = 1}^i (c_j - \frac{T}{M}) } \Big|$$

$$\sum_{i=1}^{n-1} \Big| { \sum_{j=1}^i A_j } \Big| = \sum_{i=1}^{n-1} | { S_i } | \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和，即 } S_i = \sum_{j=1}^i A_j$$

1. 出现一个环这种方案肯定不是最优解，因为给出去的纸牌经过一圈收回来了，显然浪费了操作次数我们在这个环上断开交易数量最小的一条交换边，并使其他边减少该边的交换数量，必然不会使方案变差

2. 出现一个点到达另一个点有两条路径我们可以断开起点两条出边中 $val = cnt \times w$ 最小的那一套边，并该边权值累加到另一条路径的每一条边上，其结果不会变差（其中 $cnt$ 是起点到终点路径上经过的点数，$w$ 是这条边的权重）

$$\begin{matrix} A_1 & S_1 \\ A_2 & S_2 \\ \cdots & \cdots \\ A_k & S_k \\ A_{k+1} & S_{k+1} \\ \cdots & \cdots \\ A_n & S_n \end{matrix}$$

$$\begin{matrix} A_{k+1} & S_{k+1} - S_k \\ \cdots & \cdots \\ A_n & S_n - S_k \\ A_1 & S_1 + S_n - S_k \\ A_2 & S_2 + S_n - S_k \\ \cdots & \cdots \\ A_k & S_k + S_n - S_k \\ \end{matrix}$$

$$\sum_{i=1}^n |S_i - S_k| \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和，即 } S_i = \sum_{j=1}^i A_j$$

#### 思路二：推公式

$$Min = min\sum\limits_{i=1}^nx_i$$

$$Min = min\sum\limits_{i=1}^n|x_1 - c_i|$$

$$c_n = avg - a_n，c_{i-1} = c_i + avg - a_{i-1}，c = 0$$

$$\begin{cases} avg =& c_1 - d_1 + d_n \\ avg =& c_2 - d_2 + d_1 \\ \cdots \\ avg =& c_{n-1} - d_{n-1} + d_{n-2} \\ avg =& c_{n} - d_{n} + d_{n-1} \end{cases} \qquad \Rightarrow \qquad \begin{cases} d_1 &= c_1 - avg + d_n \\ d_2 &= c_2 - avg + d_1 \\ \cdots \\ d_{n-1} &= c_{n-1} - avg + d_{n-2} \\ d_n &= c_{n} - avg + d_{n-1} \end{cases}$$

$$\begin{cases} d_1 =& c_1 - avg + d_n \\ d_2 =& \sum\limits_{i=1}^2 c_i - 2 \times avg + d_n \\ \cdots \\ d_{n-1} =& \sum\limits_{i=1}^{n-1} c_i - (n-1) \times avg + d_n \\ d_n =& \sum\limits_{i=1}^{n} c_i - n \times avg + d_n \end{cases}$$

$$\sum_{i=1}^n d_i = \sum_{i=1}^n |d_n - \sum_{j=1}^i A_j| = \sum_{i=1}^n |d_n - S_i|$$ ## 峰谷类

### 1. AcWing 1055. 股票买卖 II
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9435314,"math_prob":0.9997799,"size":19885,"snap":"2023-40-2023-50","text_gpt3_token_len":17704,"char_repetition_ratio":0.06770283,"word_repetition_ratio":0.08651226,"special_character_ratio":0.25853658,"punctuation_ratio":0.061185468,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99791706,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28],"im_url_duplicate_count":[null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-07T07:11:22Z\",\"WARC-Record-ID\":\"<urn:uuid:99445e0c-4339-4617-b681-0dd856fb5ea0>\",\"Content-Length\":\"274179\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a134f995-554c-4044-b452-33dc33fbb9f1>\",\"WARC-Concurrent-To\":\"<urn:uuid:31f46cd9-1997-4d51-8e03-1abe3853e4d4>\",\"WARC-IP-Address\":\"76.76.21.93\",\"WARC-Target-URI\":\"https://www.dreamgo.fun/2023/04/06/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E8%AF%BE-6-%E8%B4%AA%E5%BF%83/\",\"WARC-Payload-Digest\":\"sha1:A5OLZG2ZOSHWOIQ3DFR4SSNJCV4K6A6D\",\"WARC-Block-Digest\":\"sha1:OV6YS7HK3VH2IRBBZ3ZL4EMCTF3MJR6O\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100650.21_warc_CC-MAIN-20231207054219-20231207084219-00788.warc.gz\"}"}