贪心

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心问题先分析局部情况，寻找局部最优解，循环求解局部最优解就能得到全局最优解

贪心问题往往是单极值的凸问题。

贪心问题往往要先进行排序，数据要有序才方便分析，能迭代的前提是建立某种迭代的标准(迭代顺序和优化测度）。

贪心是一种梯度下降的方法，想要求出极值，我们首先要建立自己的梯度和更新的机制，然后需要迭代求解。

迭代的起始点往往是有优化测度有关的某一状态属性处于最值的点（局部最优解）。

贪心问题首先要有局部情况的研究进行猜想和多种尝试，再证明局部最优即即能得到全局最优

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

贪心的题目跳跃性很强，结论证明较难。首先的思路是转化套类型题，其次时进行猜测。

算法思路

贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。

贪心算法一般按如下步骤进行：

建立数学模型来描述问题。要确定优化测度。
把求解的问题分成若干个子问题（集合划分）。是迭代划分的。
对每个子问题求解，得到子问题的局部最优解。
把子问题的解局部最优解合成原来解问题的一个解。

算法特性

贪心算法可解决的问题通常大部分都有如下的特性：

有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。
随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
最后，目标函数给出解的值。常用技巧：排序、维护最优解

证明方法

贪心是一种在每次决策时采取当前意义下最优策略的算法，因此，使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心算法的正确性的证明手段有：

1.微扰(邻项交换)

证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。

2.范围缩放

证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。

3.决策包容性

证明在任何局面下，作出局部最优决策以后，在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之，这个局部最优策略提供的可能性包含其他所有策略提供的可能性。

4.反证法

5.数学归纳法

6.调整法

迭代顺序与维护方法的确定

贪心问题往往涉及两个对象和一个标准，对于对象和标准都需要动态维护，维护的方法包括变量存储、排序、利用堆等数据结构等。有的问题只有一个对象的维护比较复杂，有的则两个都要仔细设计维护方法。

贪心问题一般首先要确定候选对象集（可行集、或需处理的对象集合、或使目标函数更新的对象集合），然后再在候选对象集中选择最优对象。前者需要一个判断可行性的函数或判断是否需处理的函数，后者需要确定最优策略。同时，要考虑对象之间是否存在替换性，候选对象是否可以被丢弃。有的问题只用在候选对象集中取最优解，其余对象都可以被丢弃（候选对象集每次动态变化）。有的问题则候选对象集就是剩余所有对象，且每个对象都要被处理，不能被丢弃。候选对象是否可丢弃对于迭代顺序影响很大。（会影响如何维护对象）

采用合适的迭代顺序是为了方便能够在一遍遍历的同时解决问题，因此就必须符合求解的需求。同时迭代的顺序还取决于对象的问题难度。不同问题，迭代顺序的针对的目的是不同的。有些问题必须首先确定候选对象集，因此我们迭代的顺序就最好满足候选对象和非候选对象（可行与不可行、需处理与不需处理、影响目标函数更新与不影响更新）的二段性（即临界点以左都是候选，避免候选和非候选的交错。由于对象不能随意丢弃，先遍历到的非候选对象在后续处理时可能变成候选对象，这就带来对象的维护难题）。然而有些问题，每个对象都必须进行处理，候选对象集就是剩余所有对象，这时就需要直接按照所有对象的最优性顺序迭代（如果不按最优性顺序，就需要对遍历到的其他对象进行维护，不能丢弃，因此就增加维护难度）。往往候选集中其他对象后面可能还会用到，不能丢弃时，就要按照候选集最优性顺序迭代。

总之，迭代顺序的选取是为了降低维护候选对象集的难度，同时方便是否为候选的判断，使问题通过循环遍历直接解决。

时间复杂度

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

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

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

区间问题

区间问题是常见的贪心问题模型。面对复杂问题，我们要尝试去除无关背景，专注本质，尝试转换为区间问题。

贪心并不是直接就能做的，一些预处理技巧都会被使用。

区间问题往往需要先进行排序。进行了排序才方便进行分析和讨论，才能进行求解。为了方便求极值。显然，数据要有序才方便分析，能迭代的前提是建立某种迭代的标准。

要么按照左端点排序，要么按照右端点进行排序，要么就是双关键字排序。

证明可以采用反证法、夹逼法、同一法、调整法、归纳法等

贪心问题往往不需要太过复杂的策略，如果选择标准太过于复杂麻烦，约束太多则往往不对

1. AcWing 905. 区间选点

解决思路：

将每个区间按照右端点从小到大排序
从后往前依次枚举每个区间

首先，我们要确定选择标准。为什么是按照右端点而不是按照左端点。

贪心的解首先是可行的解，每个区间一定要被选到，即每个区间在其结束之前要被选择到，且最优的选择时刻是其最晚被选择的时刻，即其右端点（结束的时刻）。

由此我们确定选择标准是右端点在最前面的点，点的位置为右端点。

而左端点在被选区间右端点前的点也都会被选中，为了避免重复，集合重新划分的标准是将候选集合中区间的左端点与被选区间的右端点进行比较。

这里候选对象集是需处理的区间的集合，即左端点大于当前最右端点的集合，且候选集中非最优解后续仍可能会被用到，不能丢弃，因此迭代顺序为候选集中最优性顺序，即将每个区间按照右端点从小到大排序。

// 贪心——区间选点
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;

// 重载结构体或类的比较运算符
struct Range{ // 注意这里使用sort进行排序的技巧
    int l, r;
    bool operator< (const Range &W)const{
        return r < W.r; // 升序排列
    }
}range[N];
/*
// 定义比较函数
bool mycmp(Range a, Range b){
    return a.r < b.r;
}
*/

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);
    // sort(range, range + n, mycmp);

    // ed维护标准
    int res = 0, ed = -2e9; // ed为选择标准和划分标准，表示被选区间右端点，首先初始化为极小值
    for (int i = 0; i < n; ++ i)
        if (range[i].l > ed)
        {
            res ++ ;
            ed = range[i].r; // 标准更新
        }

    printf("%d\n", res);

    return 0;
}

sort()函数自定义排序

C++ 中的sort()排序函数用法

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

//对 [first, last) 区域内的元素做默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);

//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

其中，first 和 last 都为随机访问迭代器，它们的组合 [first, last) 用来指定要排序的目标区域；另外在第 2 种格式中，comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater从大到小排序），也可以是自定义的排序规则。

升序：sort(begin,end,less())
降序：sort(begin,end,greater())

自定义排序规则的方法

方法一：定义比较函数（最常用）

//情况一：数组排列
int A[100];
bool cmp1(int a,int b)//int为数组数据类型
{
    return a>b;//降序排列
    //return a<b;//默认的升序排列
}
sort(A,A+100,cmp1);

//情况二：结构体排序
Student Stu[100];
bool cmp2(Student a,Student b)
{
    return a.id>b.id;//按照学号降序排列
    //return a.id<b.id;//按照学号升序排列
}
sort(Stu,Stu+100,cmp2);

注：比较方法也可以放在结构体中或类中定义。

方法二：重载结构体或类的比较运算符

//情况一：在结构体内部重载
typedef struct Student{
    int id;
    string name;
    double grade;

    bool operator<(const Student& s)
    {
        return id>s.id;//降序排列
        //return id<s.id;//升序排列
    }
};

vector<Student> V;
sort(V.begin(),V.end());

//情况二：在外部重载 友元函数
vector<Student> V;
bool operator<(const Student& s1, const Student& s2)
{
    return s1.id>s2.id;//降序排列
    //return s1.id<s2.id;//升序排列
}
sort(V.begin(),V.end());

注意：一定要重载<运算符，因为系统默认是降序，用的是<运算符。

方法三：声明比较类（少用）

struct Less
{
    bool operator()(const Student& s1, const Student& s2)
    {
        return s1.id<s2.id; //升序排列
    }
};
sort(sutVector.begin(),stuVector.end(),Less());

代码举例

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
//以普通函数的方式实现自定义排序规则
bool mycomp(int i, int j) {
    return (i < j);
}
//以函数对象的方式实现自定义排序规则
class mycomp2 {
public:
    bool operator() (int i, int j) {
        return (i < j);
    }
};

int main() {
    std::vector<int> myvector{ 32, 71, 12, 45, 26, 80, 53, 33 };
    //调用第一种语法格式，对 32、71、12、45 进行排序
    std::sort(myvector.begin(), myvector.begin() + 4); //(12 32 45 71) 26 80 53 33
    //调用第二种语法格式，利用STL标准库提供的其它比较规则（比如 greater<T>）进行排序
    std::sort(myvector.begin(), myvector.begin() + 4, std::greater<int>()); //(71 45 32 12) 26 80 53 33
   
    //调用第二种语法格式，通过自定义比较规则进行排序
    std::sort(myvector.begin(), myvector.end(), mycomp2());//12 26 32 33 45 53 71 80

    //输出 myvector 容器中的元素
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
        std::cout << *it << ' ';
    }
    return 0;
}

python

def main():
    n = int(input())
    # 按右端点大小排序
    rg = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1])
    
    res = 0
    ed = - float('inf')
    for l, r in rg:
        if l > ed:
            ed = r
            res += 1
    print(res)

if __name__ == "__main__":
    main()

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

该题的证明应用到了区间选点的结论，本质两题是等价的：

最大不相交区间数==最少覆盖区间点数

将每个区间按照右端点从小到大进行排序
初始时，用ed表示当前放置在数轴上的点的位置，开始初始化为无穷小，表示没有放置，此时数轴上没有点
依次枚举排序好的每个区间。如果区间的左端点大于当前放置点的位置，说明当前点无法覆盖区间，则把点的位置更新成该区间的右端点，表示在该区间的右端点放置一个新的点，同时更新点的个数

// 贪心——最大不相交区间数量
// 本题代码与区间选点这题完全一样
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return r < W.r;
    }
}range[N];
/*
bool cmp(Range a, Range b){
    return a.r < l.r;
}
*/

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> range[i].l >> range[i].r;

    sort(range, range + n);
    // sort(range, range + n, cmp);

    int res = 0, ed = -2e9;// ed为选择和划分的标准
    for (int i = 0; i < n ; ++ i)
        if (range[i].l > ed){ // 选择标准——左端点大于已有边界（最大右端点）的第一个区间
            ed = range[i].r; // 标准更新——最大右端点
            res ++;
        }

    printf("%d\n", res);
    return 0;
}

Pyhton

def main():
    n = int(input())
    rg = sorted([list(map(int, input().split())) for _ in range(n)], key = lambda x: x[1])
    
    res = 0
    ed = -float("inf")
    for l, r in rg:
        if l > ed:
            res += 1
            ed = r
    print(res)

if __name__ == "__main__":
    main()

3. AcWing 906. 区间分组

本题的划分标准是区间的左端点要大于小组最大右端点才能入组，如果小于所有组的最大右端点就要重新建一个小组。

而优化的关键在于让哪个区间优先入组，并且当一个区间能够进入多个小组时该如何选择。这里的决策是优先将候选集合中左端点最小的区间入组，并且将其加入到最大右端点最小的小组，这样才能避免冲突。这是因为该小组可能是该区间唯一能进入的小组，如果它不进入，就要另建一个小组，不是最优选择。

由此，我们要做以下工作：

对区间按左端点由小到大排队，在前优先入组
记录每个小组的最大右端点作为入组标准，并且要维护所有小组中最小的最大右端点
将候选集合中左端点最小的区间加入到最大右端点最小的小组

这里的一个难点是如何维护最小的最大右端点，维护最大值或最小值往往要采用堆排序的方法。

不需要真的分组，组的个数等于堆中元素个数。

// 贪心——区间分组，利用了小根堆维护最大右端点的最小值
#include <iostream>
#include <algorithm>
#include <queue>// STL中的堆即优先队列

using namespace std;

const int N = 100010;

int n;

struct Range{
    int l, r;
    bool operator< (const Range &W){
        return l < W.l;// 按左端点排序
    }
}range[N];

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);

    priority_queue<int , vector<int>, greater<int>> heap;
    // 使用小根堆

    for (int i = 0; i < n; ++ i){
        auto r = range[i];
        if (heap.empty() || heap.top() >= r.l) heap.push(r.r); 
        // 划分标准：区间左端点是否大于最小Max_r
        // 先建一个小组 <==> 在堆中直接插入该区间的右端点作为堆的新元素
        // 组的个数等于堆中元素个数
        // 注意取等问题，端点相交也不行
        else
        {
            heap.pop(); // 删除原有标准
            heap.push(r.r); // 插入并更新标准
        }
        // 注意这里所有元素都一定会被分组
    }
    printf("%d\n", heap.size());
    // 堆的元素数 == 最大右端点数 == 小组数

    return 0;
}

C++优先队列

c++优先队列(priority_queue)用法详解

优先队列priority_queue即堆，默认是大根堆。在头文件< queue> 中。

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

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

和队列基本操作相同:

top() 访问队头元素
pop() 弹出队头元素
empty() 队列是否为空
size() 返回队列内元素个数
push() 插入元素到队尾 (并排序)
emplace() 原地构造一个元素并插入队列

和队列一样，没有clear()函数

定义：priority_queue<Type, Container, Functional>

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

改成小根堆的方法：

使用负数
priority_queue<int , vector, greater> heap

//升序队列
priority_queue <int, vector<int>, greater<int>> q;
//降序队列
priority_queue <int, vector<int>, less<int>>q;

// greater和less是std实现的两个仿函数
//（就是使一个类的使用看上去像一个函数。
// 其实现就是类中实现一个operator()，
// 这个类就有了类似函数的行为，就是一个仿函数类了）

Python

import heapq # 优先队列

def main():
    n = int(input())
    rg = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
    
    heap = []
    for l, r in rg:
        if not heap or l <= heap[0]:
            heapq.heappush(heap, r)
        else:
            heapq.heapreplace(heap, r)
    print(len(heap))

if __name__ == "__main__":
    main()

Python优先队列

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

堆是一种基本的数据结构，堆的结构是一棵完全二叉树，并且满足堆积的性质：每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。

堆结构分为大顶堆和小顶堆，在heapq中使用的是小顶堆：

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

在heapq库中，heapq使用的数据类型是Python的基本数据类型 list ，要满足堆积的性质，则在这个列表中，索引 k 的值要小于等于索引 2k+1 的值和索引 2k+2 的值(在完全二叉树中，将数据按广度优先插入，索引为k的节点的子节点索引分别为2k+1和2k+2)。在heapq库的源码中也有介绍，可以读一下heapq的源码，代码不多。

使用Python实现堆排序可以参考：https://blog.csdn.net/weixin_43790276/article/details/104033696

完全二叉树的特性可以参考：https://blog.csdn.net/weixin_43790276/article/details/104737870

二、使用heapq创建堆

# coding=utf-8
import heapq

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
    heapq.heappush(heap, num)
print("array:", array)
print("heap: ", heap)
 
heapq.heapify(array)
print("array:", array)

运行结果：

1
2
3

array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap:  [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
array: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]

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

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

heapify(array)，直接将数据列表调整成一个小顶堆(调整的原理参考上面堆排序的文章，heapq库已经实现了)。

这里注意heapq不会创建存储变量，而必须将存储变量传入，heap只负责排序。当然也可以有heap = heapq。heapify([])的写法，总之一定要有传入存储变量

两种方法实现的结果会有差异，如上面的代码中，使用heappush(heap, num)得到的堆结构如下。

heappush

使用heapify(array)得到的堆结构如下。

heapify

不过，这两个结果都满足小顶堆的特性，不影响堆的使用(堆只会从堆顶开始取数据，取出数据后会重新调整结构)。

三、使用heapq实现堆排序

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
    heapq.heappush(heap, num)
print(heap[0])
# print(heapq.heappop(heap))
heap_sort = [heapq.heappop(heap) for _ in range(len(heap))]
print("heap sort result: ", heap_sort)

运行结果：

1 2	5 heap sort result: [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

先将待排序列表中的数据添加到堆中，构造一个小顶堆，打印第一个数据，可以确认它是最小值。然后依次将堆顶的值取出，添加到一个新的列表中，直到堆中的数据取完，新列表就是排序后的列表。

heappop(heap)，将堆顶的数据出堆，并将堆中剩余的数据构造成新的小顶堆。

四、获取堆中的最小值或最大值

array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heapq.heapify(array)
print(heapq.nlargest(2, array))
print(heapq.nsmallest(3, array))

运行结果：

1 2	[50, 45] [5, 7, 10]

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

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

这两个方法除了可以用于堆，也可以直接用于列表，功能一样。

五、使用heapq合并两个有序列表

array_a = [10, 7, 15, 8]
array_b = [17, 3, 8, 20, 13]
array_merge = heapq.merge(sorted(array_a), sorted(array_b))
print("merge result:", list(array_merge))

运行结果：

1	merge result: [3, 7, 8, 8, 10, 13, 15, 17, 20]

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

六、heapq替换数据的方法

array_c = [10, 7, 15, 8]
heapq.heapify(array_c)
print("before:", array_c)
# 先push再pop
item = heapq.heappushpop(array_c, 5)
print("after: ", array_c)
print(item)
 
array_d = [10, 7, 15, 8]
heapq.heapify(array_d)
print("before:", array_d)
# 先pop再push
item = heapq.heapreplace(array_d, 5)
print("after: ", array_d)
print(item)

运行结果：

before: [7, 8, 15, 10]
after:  [7, 8, 15, 10]
5
before: [7, 8, 15, 10]
after:  [5, 8, 15, 10]
7

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

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

两个方法都是即入堆又出堆，只是顺序不一样，可以用于替换堆中的数据。具体的区别可以看代码中的例子。

4. AcWing 907. 区间覆盖

本题的一大特点是候选区间是变化的，相当于有三个区间和两次筛选，这和区间分组这题类似的，但通过进行排序我们仍能非常方便的进行枚举而不用回溯。

本题使用调整法证明。

要区分迭代顺序和优化测度（选择函数）。

本题迭代顺序是所有区间按左端点从小到大顺序，选择函数（最优策略）则是选择能覆盖start的区间中，右端点最大的区间。

迭代顺序要便于最优策略的实施。如果按右端点从小到大顺序排序，可以发现

// 贪心——区间问题——区间覆盖   
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed, n;// st、ed为待覆盖区间的左右端点
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false; // 标记是否能成功覆盖
    for (int i = 0; i < n; ++ i)
    {
        int j = i, r = -2e9; // r用于记录候选区间的最大右端点
        // 筛选候选区间
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r); // 记录候选区间的最大右端点
            ++ j;
        }

        if (r < st) // 候选区间的最大右端点与待覆盖区间的左端点比较
        {
            res = -1;
            break;
        }

        res ++ ; // 成功覆盖后，区间数增1
        st = r; // 更新选择候选区间的标准：更新待覆盖区间的左端点
        i = j - 1; // 抛弃当前候选集合中的所有区间，更新要枚举的原始区间的开始位置

        if (st >= ed) 
        {
            success = true;
            break;
        }
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}

Python

def main():
    st, ed = map(int, input().split())
    n = int(input())
    
    rg = sorted([list(map(int, input().split())) for _ in range(n)], key = lambda x: x[0])
    
    res = 0
    find = False
    i = 0
    while i < n:
        r = -float("inf")
        while i < n and st >= rg[i][0]: 
            r = max(r, rg[i][1])
            i += 1
        if r < st:
            break
        else:
            st = r
            res += 1
        if r >= ed:
            find = True
            break
    print(res if find else "-1")
    
if __name__ == "__main__":
    main()

这题的代码我自己写卡了好久，问题就在于我将判断更新Max_r和遍历候选区间。导致出错的是一些边界情况如，最后一个区间恰是要选择的最后一个区间、区间长度为0等。写代码时为了避免边界出问题或其他一些没有考虑的问题，要采用分布思想，每个不同的逻辑功能处采用单独的一段代码进行处理，分块书写，不要怕麻烦。

5. AcWing 111. 畜栏预定

本题显然是一个区间分组问题，不过要记录的信息多一点。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> P;

const int N = 50010;

struct Range{
    int l, r, x, w;
}range[N];

bool cmp1(Range a,  Range b){
    return a.l < b.l;
}

bool cmp2(Range a,  Range b){
    return a.w < b.w;
}

struct cmp3{
    bool operator() (const P &a,  const P &b){
        return a.first > b.first;
    }

};
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i){
        scanf("%d%d", &range[i].l, &range[i].r);
        range[i].w = i;
    }
    sort(range + 1, range + n + 1, cmp1);

    int res = 0;
    priority_queue<P, vector<P>, cmp3> heap;
    for (int i = 1; i <= n ; ++ i)
    {
        if (heap.empty() || heap.top().first >= range[i].l)
        {
            res ++;
            heap.push(make_pair(range[i].r, res));
            range[i].x = res;
        }
        else{
            P min = heap.top();
            heap.pop();
            heap.push(make_pair(range[i].r, min.second));
            range[i].x = min.second;
        }
    }
    sort(range + 1, range + n + 1, cmp2);
    printf("%d\n", res);
    for (int i = 1; i <= n; ++ i) printf("%d\n", range[i].x);
    return 0;
}

6. AcWing 110. 防晒

这里有两个对象——奶牛和防晒霜，所以对于两者都要进行维护和处理。

奶牛和防晒霜都有多个，为了便于分析，显然要一瓶一瓶防晒霜的处理。

奶牛需要强度实际上是一个区间，所以这是区间问题。

显然最基本的，需求低的牛涂作用低的防晒霜，所以防晒霜和奶牛都要排序才方便处理。每个防晒霜都有其可作用奶牛的集合，我们以防晒霜为标准从左到右筛选奶牛，确定候选集合。需求的左端点小于此防晒霜、右端点大于当前防晒霜才可以涂。

对于可以涂的候选集合，右端点小的一定会优先涂。这是因为如果右端点小的可以用后续的防晒霜，右端点大的也一定可以。反之则不行。有最优方案是能涂完就涂完，所以按照右端点顺序依次涂，直至涂完。

本题我最初还是分析错了，我忽略了一个问题：有些右端点偏左的牛左端点可能偏右，可能不能涂当前的防晒霜，但可以涂下一个防晒霜，这就出现了回溯问题，无法循环迭代。但是牛按右端点排序是没问题，因为就算只能涂下一个防晒霜，也一定优先涂，符合要求的牛右端点偏左的一定优先涂，且一定涂从左到右第一个符合的防晒霜。这意味我们需要双循环，对防晒霜也采用最优策略：从左到右排序，第一个大于左端点的还有剩余的防晒霜一定涂給当前的牛。

这样我们就可以发现我们之前的致命错误：牛和防晒霜基本是同地位的，对两者都要筛选最优来配对，不能只考虑牛或防晒霜。双变量（双筛选）则意味着双循环。

处理双循环的另一个关键问题是谁为内循环，谁为外循环。本题牛为外循环，很简单，因为牛有两个端点，防晒霜只有一个点坐标。而本题内循环本质上会出现回溯，需要进行标记。如果牛作为内循环，就会出现比较复杂的回溯，而防晒霜作为内循环比较容易标记

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2510;

struct Range{
    int l, r;
    bool operator< (const Range &w)const{
        return r < w.r;
    }
}range[N];

struct Cover{
    int c, n;
    bool operator< (const Cover &w)const{
        return c < w.c;
    }
}cover[N];

int main(){
    int c, l;
    cin >> c >> l;
    for (int i = 0; i < c; ++ i)
        scanf("%d%d", &range[i].l, &range[i].r);
    for (int i = 0; i < l; ++ i)
        scanf("%d%d", &cover[i].c, &cover[i].n);
    
    sort(range, range + c);
    sort(cover, cover + l);
    
    int res = 0;
    for (int i = 0; i < c; ++ i){
        int j;
        bool st = false;
        for (j = 0; j < l; ++ j)
            if (cover[j].c >= range[i].l && cover[j].n){
                st = true;
                break;
            }
        if (st && cover[j].c <= range[i].r){
            res ++;
            cover[j].n--;
            
        }
    }
    printf("%d\n", res);
    return 0;
}

7. AcWing 112. 雷达设备

逆向思维

本题实际上可以转化为“区间选点”问题，并不难然而我却被题目的表述形式卡住了。

本题雷达站有一特性：都固定在x轴上，是一维；而海岛则是二维的，可以分布在x轴上方任意位置。

本题的要求是让雷达覆盖小岛，雷达是动的，但规格确定。如果直接去思考如何让雷达去覆盖小岛是很麻烦的，因为覆盖的范围是二维的圆，寻找一个雷达能够覆盖到的小岛很不方便。

二维问题过于复杂，尝试转化为一维。关键在于入手对象的选取。多个对象时，要从简单的对象入手。前面AcWing 110. 防晒这道题也是类似，对于防晒霜和奶牛，我们首先从防晒霜入手而不是奶牛。

然而考虑到已知条件，我们完全可以预处理以下，找到每个小岛可以被雷达覆盖时，雷达所需要的临界条件（此时是一维的条件了），此时我们就可以化二维为一维，大大简化问题。每个小岛能否被覆盖此时就对应于一个一维区间范围，问题也就转化为了“区间选点”问题。

本题再次反映了我在思考问题时思维的僵化，要学会在理解题目的基础上对题目进行一定的处理，实现问题表述和思考逻辑的转化，充分简化问题。

本题我们用到了逆向思维、二维化一维的思维，转化化归为基本模型的思维，利用已知条件预处理从而简化条件和问题的方法。

1130_2b828e0e3d-雷达设备2

// 贪心——区间问题——AcWing 1247. 后缀表达式
// 利用逆向思维、二维化一维的思维可以转化化归为区间选点的基本问题
// 贪心——区间问题——AcWing 1247. 后缀表达式
// 利用逆向思维、二维化一维的思维可以转化化归为区间选点的基本问题
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1010;

struct Range{
    double l, r;
    bool operator< (const Range &W)const{
        return r < W.r;
    }
}range[N];

int main(){
    int n, d;
    cin >> n >> d;
    bool failed = false;
    for (int i = 0 ; i < n; ++ i){
        int x, y;
        scanf("%d%d", &x, &y);
        if (d < y)
            failed = true;
        else {
            double len = sqrt(d * d - y * y);
            range[i].l = x - len;
            range[i].r = x + len;
        } 
    }
    
    if (failed)
        puts("-1");
    else{
        sort(range, range + n);

        int res = 0; 
        double ed = -1e20;
        for (int i = 0; i < n; ++ i)
            if (range[i].l > ed){
                ed = range[i].r;
                res ++;
            }
        printf("%d\n", res);
    } 
    return 0;
}

Huffman树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树的关键特性是带权路径最小，凡是问题要求解的量可以转化为二叉树的带权路径的，就可以用哈夫曼树来求其最小值。

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

构造过程

哈夫曼树的构造过程使用的是贪心的策略

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

构建哈弗曼树的算法实现

构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。

查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：

如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
如果介于两个结点权重值之间，替换原来较大的结点；

由于哈夫曼树是二叉树，我们可以使用优先队列（堆）来实现，每次更新时，会取出最小的两个值，并将其和重新放入集合，为了便于维护排序，可使用小根堆。

权重越小的点，放的深度越深。

1. AcWing 148. 合并果子

合并堆的过程可以被视作由底向上构建树的过程，总代价就是树的带权路径，因此可以构建Huffman树求最小值。

使用小根堆维护所有果子，每次弹出堆顶的两堆果子，并将其合并，合并之后将两堆重量之和再次插入小根堆中。

每次操作会将果子的堆数减一，一共操作 $n - 1$ 次即可将所有果子合并成 1 堆。每次操作涉及到 2 次堆的删除操作和 1 次堆的插入操作，计算量是 $O(logn)$。因此总时间复杂度是 $O(nlogn)$。

微扰法证明

// 贪心——huffman数——合并果子
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);

    priority_queue<int , vector<int>, greater<int>> heap;
    // 小根堆
    while (n --){
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    // res 即带权路径和WPL， 在本题中每个结点到其父节点的路径权重为其自身值得大小

    // 构建哈夫曼树
    // 只剩根节点时即结束
    while (heap.size() > 1){ 
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop(); 
        // 取出最小的两个结点；注意priority_queue.pop()是没有返回值的
        res += a + b;
        // WPL要增加这两个节点到其合并出的父节点的路径权重（即各自的值大小）
        heap.push(a + b);
        // 将新生成的结点再次放入集合（堆）
    }

    printf("%d\n", res);
    return 0;
}

Python

import heapq

def main():
    n = int(input())
    # 使用小根堆维护哈夫曼树节点
    heap = list(map(int, input().split()))
    
    heapq.heapify(heap)
    
    res = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        heapq.heappush(heap, a + b)
        res += a + b
    print(res)
    
if __name__ == "__main__":
    main()

排序不等式

这种题型使用先进行排序，利用排序不等式从小到大即为最优方案。

排序不等式（Rearrangement Inequality）又称排序原理，是数学上的一种不等式。排序不等式表述如下。

设有两数列$a_1, a_2, \cdots, a_n$和$b_1, b_2, \cdots, b_n$，满足$a_1\leq a_2\leq \cdots\leq a_n$，$b_1 \leq b_2\leq \cdots\leq b_n$， $c_1,c_2,\cdots,c_n$是$b_1, b_2, \cdots, b_n$的乱序排列，则有：
$$
\sum\limits^{n_{i=1}a_ib_{n+1-i}\leq\sum\limits}n_{i=1}a_ic_i\leq\sum\limits^n_{i=1}a_ib_i
$$
当且仅当$a_i=a_j$ 或 $b_i=b_j(1\leq i,j\leq n)$时等号成立。

简单说就是按照从小到大的“顺序”相乘的和最大；按照相反顺序，也就是“逆序”相乘的和最小；混乱顺序则处于二者之间。(正序和大于等于乱序和，乱序和大于等于逆序和)

证明使用调整法（微扰），推不等式

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
$$

代价可以直接中公式求出。得到公式后既可以利用不等式放缩得到最优解情况，这里利用排序不等式即可。

由此，我们可以得到贪心策略：按照从小到大的顺序排列，总时间最小

// 贪心——推公式——排队打水
// 利用了排序不等式
// 贪心策略：按照从小到大的顺序排列，总时间最小
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL; // 注意爆int

const int N = 100010;

int n;
int t[N];

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);

    sort(t, t + n);
    reverse(t, t + n);

    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * i;
    // 没有reverse，则写成： res += t[i] * (n - i - 1);

    printf("%lld\n", res);

    return 0;
}

Python

def main():
    n = int(input())
    nums = sorted(list(map(int, input().split())))
    
    res = sum(nums[i] * (n - i - 1) for i in range(n))
    print(res)
    
if __name__ =="__main__":
    main()

绝对值不等式

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

$$
||a| - |b|| ≤ |a+b| ≤ |a|+|b|
$$
当且仅当$ ab≤0 $时左边等号成立，$ab≥0$ 时右边等号成立

几何意义
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. 货仓选址

设出所有点的值，写出对应公式，从公式的角度推导出如何取最小值

这题推导时变形的非常巧妙，对我个人而言还是很难想到的。同时本题是很基本的模板和类型题，做法需要铭记。

中位数有非常优秀的性质，比如说在这道题目中，每一个点到中位数的距离，都是满足全局的最优性，而不是局部最优性。

我们设在仓库左边的所有点，到仓库的距离之和为pp,右边的距离之和则为qq，那么我们就必须让p+qp+q的值尽量小。

当仓库向左移动的话，pp会减少xx，但是qq会增加n−xn−x，所以说当为仓库中位数的时候,p+qp+q最小。

本题的解决关键是推出目标的公式表示，然后再利用绝对值不等式。为此先把所有点假设表述出来。推出公式后有个小难点时这里利用不等式时也是从局部的思路来思考的，而不是整体一起应用不等式（分组的技巧）。本题证明的核心就在于分组。

// 贪心——推公式——货仓选址
// 本题使用绝对值不等式
// 排序+中位数
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int q[N];

int main(){
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n ; ++ i) scanf("%d", & q[i]);

    sort(q, q + n);

    int res = 0;

    for (int i = 0; i < n; ++ i) res += abs(q[i] - q[n >> 1]);// q[n/2]
    // abs(q[i] - q[n/2])对于n为就奇偶都成立
    // 如果有奇数个数，则一定在中位数处
    // 如果有偶数个数，则一定在中间两个数之间，包括端点，所以取前一个数q[n /2]没问题
    
    printf("%d\n", res);

    return 0;
}

Python

def main():
    n = int(input())
    nums = sorted(list(map(int, input().split())))
    mid = n // 2
    
    # res = 0
    # for i in range(mid):
    #     res += nums[n - i - 1] - nums[i] 
    print(sum([nums[n - i - 1] - nums[i] for i in range(mid)]))
    
    # 切片写法
    # if n & 1:
    #     nums = nums[:mid] + nums[mid+1:]
    # print(sum(nums[mid:]) - sum(nums[:mid]))
    
if __name__ == "__main__":
    main()

拓展与其他写法

推公式

很多贪心问题都是先推公式，然后利用不等式的原理，求出最优解，而不是从直觉上想

要对题目进行量化表示，明确目标函数和约束条件，进行变形和推导，同时利用一些常用的不等式等数学技巧，推出相应公式，从公式的角度应用不等式的原理。

常用不等式有均值不等式、调和不等式、柯西不等式、排序不等式、绝对值不等式等。

为了写出公式，首先要把所有对象对应量表示出来。有些时候可以直接写出去目标函数全局公式，有些时候则不能。对于不方便写出全局公式的，可以使用邻项交换法等进行表示和分析。

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

本题所要求的其实就是找到一种最优的排序方法。

考虑到贪心策略，我们先研究局部的排序方法，最小的局部即相邻的两个项如何排序。

这里关键要意识到相邻的两项互换的话并不会影响其他项的值，只会影响这两项的值，因此自然想到用邻项交换法。

邻项交换法（微扰）求某个排列问题中考虑交换两个相邻项看哪种更优。比较微扰后的代价和之前的代价哪一个更大。这种方法不仅可用于证明贪心策略的有效性，也可用于进行问题的推导。

这是一种类似冒泡排序的思想，每次相邻项的交换都使答案更优，而当全排好后相邻的都达到最优，而全局最大值就是这些相邻对最大值之一，于是全局最大值能够最小。

本题使用邻项交换法，先求出使得相邻两项最优的排序方法。这需要进行数学推导，表示出目标函数、约束条件、已知量，进行分类讨论，可以非常容易的推到出最有条件。只需注意推导时要灵活代数变形。（具体略，可参考AcWing 125. 耍杂技的牛（严密推导，自然分析，不需要直觉））

经过数学推导，可以发现最优条件是将$w + s$小的放上面，大的放下面。同时迭代思路是按照这种思路进行全排序，按照$w_i + s_i$从小到大的顺序排，风险系数一定是最小的。

// 贪心——推公式——耍杂技的牛
// 重点利用了邻项交换（微扰）法进行推导和证明
// 贪心策略：按照 w + s从小到大的顺序排
#include <iostream>
#include <algorithm>
#include <utility> // 使用pair

using namespace std;

typedef pair<int, int> PII; 

const int N = 50010;

int n;

PII cow[N];

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i){
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }

    sort(cow, cow + n);
    // 使用sort()对pair排序时，默认对first升序，当first相同时对second升序；
    // 但需注意这里不要误解为：如果强度和重量之和相等，必须按照重量从小到大排
    // 实际上我们推出的条件是按w + s来排序的，当其相等时，随意排或按照w排或按照s排都可以
    // 而这里使用pair的目的不是为了双关键字排序，而仅仅是为了便于存储，(w + s, w或s)的存储方式可以方便在排序后仍能轻松得到w和s各自的值

    int res = -2e9, sum = 0; 
    for (int i = 0 ; i < n; ++ i){
        int s = cow[i].first - cow[i].second, w = cow[i].second;
        res = max(res, sum - s);
        sum += w; // 计算前 i - 1项的重量和
    }
    printf("%d\n", res);

    return 0;
}

C++ pair

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

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

其标准库类型–pair类型定义在#include 头文件中，定义如下：

类模板：template<class T1,class T2> struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

功能：pair将一对值(T1和T2)组合成一个值，

这一对值可以具有不同的数据类型（T1和T2），
两个值可以分别用pair的两个公有函数first和second访问。

使用sort()对pair排序时，默认对first升序，当first相同时对second升序；

Python

def main():
    n = int(input())
    data = sorted([list(map(int, input().split())) for _ in range(n)], key = lambda x: sum(x))

    
    res = -float("inf")
    sums = 0
    for w, s in data:
        res = max(res, sums - s)
        sums += w
    print(res)
    
if __name__ == "__main__":
    main()

2. AcWing 114. 国王游戏

本题与“耍杂技的牛”的解题思路基本一致，为贪心推公式的方法。

本题的目标是一种最优的排序方式，而相邻项进行比较、冒泡排序的方法不仅适用于单纯的数值排序，也适用于具有更复杂排序标准的排序问题。这种方法可以采用邻项比较（微扰）法证明。

由此，本题进行数学表示，研究相邻项比较标准的数学表达式，最终得到的贪心策略时两手的数的乘积更小的往前排，按照两手的数的乘积大小从小到大排。

但本题的一个难点是用到高精度数。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

int n;
PII p[N];

vector<int> mul(vector<int>a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

vector<int> div(vector<int>a, int b)
{
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i -- )
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x)
        {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}

vector<int> max_vec(vector<int> a, vector<int> b)
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;
    return b;
}

int main()
{
    cin >> n;
    for (int i = 0; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        p[i] = {a * b, a};
    }
    sort(p + 1, p + n + 1);

    vector<int> product(1, 1);

    vector<int> res(1, 0);
    for (int i = 0; i <= n; i ++ )
    {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }

    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    cout << endl;

    return 0;
}

处理多次询问的题许多都用前缀和

用差分实现区间操作

3. AcWing 1536. 均分纸牌

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

设一共有 M个人，每个人初始的纸牌数量为$c_i$，纸牌总数为$T$
显然当 $M∤T$时，方案不存在，现只考虑方案存在的情况

第 1 个人为了达到平均持有数，需要向第 2 个人传递 $c_1−T/M$数量的牌（正数是给，负数是拿）

第 2 个人为了达到平均持有数，需要向第 3 个人传递 $c_2−T/M+c1−T/M$数量的牌

…

第 n-1 个人为了达到平均持有数，需要向第 n 个人传递 $∑^{n−1}_{i=1}c_i−(n−1)×T/M$数量的牌

此时前 n-1 人都达到了平均数，则第 n 个人必然也达到了平均数

统计易得，最小交换次数为：

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

不妨设 $Ai=ci−T/M$，于是化简可得：

$$
\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
$$

// 贪心——前缀和——AcWing 1536. 均分纸牌
// 贪心策略：从左往右开始传递使每一个符合要求（等于平均值），符合要求则不传递
// 利用前缀和的原因：第i个和第i+1个互传后不影响s[i+1]以及往后的所有前缀和的大小
// 传递后，前i个已经符合要求，s[i] == i * ave
// 此时第i+1个如果不符合要求则s[i+1] != (i+1) * ave（至于前i个具体如何传递的不用考虑，因为s[i+1]不变）
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int s[N];

int main(){
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &s[i]);
        s[i] += s[i-1]; // 求前缀和
    }
    
    int ave = s[n] / n, res = 0;
    for (int i = 1; i < n; ++ i){
        if (s[i] - i * ave != 0){ // 选择的标准
            res ++ ;
        }
    }
    cout << res << endl;
    return 0;
}

4. AcWing 122. 糖果传递

本题首先要用数学知识进行问题的表示和推导，这一步比较难。然后通过观察推导出的代数式，我们可以联想基本题型，进而可以转化为货仓选址问题（贪心类绝对值不等式）。

首先我们进行数学分析和表示。我们用A[i]表示最初每个人的糖果数。可以发现，为了最优，一定不会出现两人之间的双向传递，只会由一人传向另一人，为此我们可以将两人之间的传递值用C[i]表示，C[i]正负都可以，正表示由前一个传给后一个，负表示由后一个传给前一个。

传递的过程是复杂的，但我们可以确定最终所有人获得糖果相同，因而$C[i] = |A[i] - ave|$一定成立。

我们优化的目标是：
$$
Min =\sum\limits^n_{i=1}|C[i]|
$$

同时分析临界情况，本问题是一个环形的糖果交换问题，则一定存在一种最优解使得某两个人之间没有交换。就是要么a给b，要么b给a，不能a给了b，b又给了a，如果存在这样的交换，就不是最优解了，可以用反证法证明。（这所以会想到这个性质是因为我们试图将环形转化为线性，更方便解决）

思路一：前缀和 + 贪心

通常，涉及连续子数组问题的时候，我们使用前缀和来解决。前缀和的作用主要体现在能快速求出一个数组中一段连续区间的和，

当序列中需要相邻项相互传递值时往往可以利用前缀和来求解。

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

环形区间的问题，第一想到的就是破环成链了

经过思考发现，一定存在一个最优解方案，环上有相邻的两个人之间没有发生交换

这部分证明如下：如果环上相邻两人全部发生交换，则会出现两种情形：（正数传递为有向边的正向方向）

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

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

一个朴素的做法是直接枚举断点的位置，然后做一遍线性纸牌均分，但是时间复杂度为 O(n^2) 不可取，需要推导

考虑在第k个人之后断开，则环化成链有：第 k+1 个人向第 k+2 个人传递 $c_k−T/M = A_{k + 1}= S_{k+1} - S_k$数量的牌（正数是给，负数是拿）

第 k+2 个人向第 k+3 个人传递 $c_{k+1}−T/M + c_k−T/M = A_{k+1} + A_k = S_{k+2} -S_k$数量的牌
…

第n个人向第1个人传递 $∑^{n}_{i=k+1}c_i−(n-k)×T/M = S_n - S_k$数量的牌

第1个人向第2个人传递 $∑^{n}_{i=k+1}c_i−(n-k+1)×T/M = S_1 + S_n - S_k $数量的牌

第k-1个人向第k个人传递 $∑^{n}{i=k+1}c_i−(n-1)×T/M = S{k-1} + S_n - S_k $数量的牌

又易知 $S_n=∑cj−n×\frac{T}{M}=0$，故求得最小步数为：

$$
∑_{i=1}^n|S_i−S_k|，其中 S_i 为 A_i 的前缀和，即 S_i=∑_{j=1}^iA_j
$$
该绝对值不等式最小值的求解，就同 “货仓选址” 异曲同工了

因此 $S_k$ 的选择，就取 $S_i$排序后的中位数即可

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

设一共有 $M$ 个人，每个人初始的纸牌数量为 $c_i$，纸牌总数为 $T$

显然当 $M \nmid T$ 时，方案不存在，现只考虑方案存在的情况

第 1 个人为了达到平均持有数，需要向第 2 个人传递 $c_1 - T / M$ 数量的牌（正数是给，负数是拿）

第 2 个人为了达到平均持有数，需要向第 3 个人传递 $c_2 - T / M + c_1 - T / M$ 数量的牌

…

第 n-1 个人为了达到平均持有数，需要向第 n 个人传递 $\sum_{i=1}^{n-1} c_i - (n-1) \times T / M$ 数量的牌

此时前 n-1 人都达到了平均数，则第 n 个人必然也达到了平均数

统计易得，最小交换次数为：

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

不妨设 $A_i = c_i - T / M$，于是化简可得：

$$
\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
$$

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

环形区间的问题，第一想到的就是 破环成链 了

经过思考发现，一定存在一个最优解方案，环上有相邻的两个人之间没有发生交换

这部分证明如下：如果环上相邻两人全部发生交换，则会出现两种情形：（正数传递为有向边的正向方向）

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

一个朴素的做法是直接枚举断点的位置，然后做一遍线性纸牌均分，但是时间复杂度为 $O(n^2)$ 不可取，需要推导

现将这 $n$ 个人的 $A_i$ 和 $S_i$ 罗列出来 $(A_i = \sum\limits_{j=1}^n (c_j - \dfrac{T}{M}), S_i = \sum\limits_{j = 1}^i A_j)$

$$
\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}
$$

考虑在第 $k$ 个人之后断开，则环化成链有：

$$
\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}
$$

又易知 $S_n = \sum c_j - n \times T / m = 0$，故求得最小步数为：

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

该绝对值不等式最小值的求解，就同上一题 “货仓选址” 异曲同工了

因此 $S_k$ 的选择，就取 $S_i$ 排序后的中位数即可

// 贪心——前缀和/推公式——AcWing 122. 糖果传递
// 贪心策略：首先破环成链，以k和k+1之间为破链处，然后从k+1开始左往右开始传递使每一个符合要求（等于平均值），符合要求则不传递
// 前缀和传递前为s[i] - s[k]，传递后为s'[i] = ave * i ，传递量为s[i] - s[k] - ave * i
// 只有s[k]为变量，可利用“货仓选址”的思路求出
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

LL s[N];

int main(){
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++ i){
        scanf("%lld", &s[i]);
        s[i] += s[i-1]; 
    }
    LL ave = s[n] / n;
    for (int i = 1; i <= n; ++ i) s[i] -= ave * i; 
    
    
    // 货仓选址：贪心、中位数
    sort(s + 1, s + n + 1);
    LL res = 0;
    
    for (int i = 1; i <= n; ++ i)
        res += abs(s[i] - s[(n+1) >> 1]);
        // 求出传递量
        
    cout << res << endl;
    return 0;
}

思路二：推公式

首先利用每个人最终都得到相同个数得糖果可以列出n个方程。然后再解线性方程组推导出结论公式，再转化为“货仓选址”问题。

不妨设每个人i向前一个传递的糖果数为$x_i$，则目标是求：
$$
Min = min\sum\limits_{i=1}^nx_i
$$

研究方程组可以发现一共有n-1个独立方程和n个未知数，因而可以用一个未知数$x_k$表示剩余的所有未知数。

整理可得：
$$
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[1] = 0
$$

第二种推导方式

这种推导方式相较于上一种，思维量小，但对公式的变形要求高，是直接统计每个点

考虑直接在环上求解，环的顺时针方向设为正方向，若边权为正，表示左向右传递；反之则是右向左传递

设 $d_i$ 表示第 $i$ 个人向第 $(i+1)\bmod n$ 传递的所有纸牌数量

传递完成后的结束是所有人的纸牌数量变成平均数，以此建立方程组有：
$$
\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}
$$
易得通项：$d_i = \sum\limits_{j=1}^{i} c_j - i \times avg + d_n = d_n + \sum\limits_{j=1}^{i} (c_j - avg) = d_n - \sum\limits_{j=1}^{i} (avg - c_j)$

不妨设 $A_i = avg - c_i, S_i = \sum\limits_{j = 1}^i A_j$，则通项可以化简为：$d_i = d_n - \sum\limits_{j=1}^{i}A_j$

则总共的操作数为：

$$
\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|
$$

由 绝对值不等式 易得：$d_n$ 应取 $S_i$ 排序后的中位数

F4178CB81B40AE8072F7F6339F541970

FFD8060DA5743944EBE8295FFB828C42

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int a[N], c[N];

int main(){
    int n;
    scanf("%d", &n);

    LL sum = 0;
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        sum += a[i];
    } 

    LL avg = sum / n;

    for (int i = n ; i > 1; -- i)
        c[i] = c[i + 1] + avg - a[i];
    c[1] = 0;
    
    sort(c + 1, c + n + 1);

    LL res = 0;
    for (int i = 1; i <= n; ++ i) res += abs(c[i] - c[(n+1)>>1]);
    printf("%lld\n",res);

    return 0;
}

5. AcWing 1235. 付账问题

本题利用了数学知识，但不要深陷入数学推导。贪心题首先还是先试试一些直觉性的局部最优策略。

本题的目标是使每个所付钱数的偏差最小，显然如果每个人带的钱数都足够，则均分最好。这利用均值不等式可证。

不同于均分问题，一旦有人带的钱数不够，就要求其他人多出钱。一种直觉性的想法时，钱不够的人肯定要把所有钱都交出，不够的钱数为了使偏差小，应由其他人均摊。

这就是我们的贪心策略。

可以发现本题不同于均分问题的一点使每个人最好按照均值支出，但均值使在变化的，一旦出现有人钱不够，其他人支出的总数就会增大，均值也相应变大。因而如果是支出顺序是无序的，支出的标准（均值）也就无法确定。

考虑到钱不够的人的支出是确定的，且所有钱不够的人算过后，其余人的支出标准也就可确定了。由此我们要进行按照钱数大小从小到大对每个人排序，从最小的开始处理

// 贪心——推公式——AcWing 1235. 付账问题
// 均值不等式 + 排序
// 贪心策略：1.按照钱数大小从小到大对每个人排序， 从最小的开始处理
// 2. 钱不够的人肯定要支出所有钱，不够的钱数由其他人均摊
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long double LD;
const int N = 500010;

int p[N];

int main(){
    int n;
    LD s = 0;
    cin >> n >> s;
    
    for (int i = 0; i < n; ++ i)
        scanf("%d", &p[i]);

    sort(p, p + n);
    LD avg = s / n, res = 0;
    for (int i = 0; i < n; ++ i){
        LD cur = s / (n - i); // 更新选择标准：剩余每人需均摊的钱
        if (p[i] < cur) cur = p[i]; 
        // 分类处理：钱不够指出所有，钱够支出当前所需的均摊的钱
        res += (cur - avg) * (cur - avg);
        s -= cur; // 更新剩余人需均摊的总钱数
    }
     printf("%.4Lf\n", sqrt(res / n));

    return 0;
}

6. AcWing 1239. 乘积最大

本题直观的策略很简单：若为正数则尽量大，负数则尽量小。

首先n个数中取n个则不用优化。

当n个数中取k个（k<n)时

为了使正数尽量大，偶数项则依次取两项负数或两项正数的乘积中最大的，奇数项则先取最大的正数项（注意不是最后处理最后一项，先处理才能保证两项乘积取得都是最大的。

成为负数只有一种可能，就是全为负数且k为奇数，显然先取最大的一个，然后依次取两项乘项最小的一对

// 贪心——排序 + 分类讨论——AcWing 1239. 乘积最大
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 9;

int a[N];

int main(){
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
    
    sort(a, a + n);

    int sign = 1, res = 1;
    int l = 0, r = n - 1;
    if (k & 1){
        res = a[r --]; 
        k--;
        // 奇数项时一定先取最大的一项
        if (res < 0) sign = -1; 
        // 序列中全为负数且要取的个数为奇数时，结果才为负数
        // 此时依次取最小的两项乘积，通过引入辅助变量sign=-1更方便统一代码
    }
    while(k){
        LL x = (LL)a[l] * a[l+1], y = (LL)a[r - 1] * a[r];
        // 排序后最大乘积项一定在两端（全为负数时最小乘积项在右端）
        if (x * sign > y * sign){ // 选择标准：大小
            res = x % mod * res % mod;
            l += 2;
        }
        else{
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }
    printf("%d\n", res);

    return 0;
}

7. AcWing 1247. 后缀表达式

本题最关键依旧是理解题目中隐含的关键性质。

为什么题目要凑出的是后缀表达式而不是中缀表达式？两者有什么最关键不同？

可以发现，后缀表达式可通过其中数字和符号的顺序来直接表示运算顺序而不需要借助括号，这在中缀时不行。

换句话说，后缀表达式等价于中缀式可以任意规定运算顺序（任意加括号）。

而这意味什么呢？我们需要进一步研究在只有加减运算时括号所起的作用。

可以发现，减号和括号得组合作用可以使得去掉括号后括号内加号变减号，减号变加号。由于括号是任意加的，不难可以想到，无论题目给出多少加号，只要存在至少一个减号，我们就能将任意数量的加号变成减号，减号数量可以为1_{N+M中的任意个（对应于加号数量可以为0}N+M-1中任意个）。

由此，最优的求解策略就是加上所有正数，减去所有负数。

注意边界情况，第一个数前无运算负，相当于一定加上第一个数，同时只要减号不为零，一定至少有一个减号。换句话说，m == 0时直接相加输出；m != 0时，一定要至少加上一个数，减去一个数，其贪心策略是先加上最大的数和减去最小的数，其余的数加上其绝对值。

再次总体说明一下，本题揭示出我们既不能局限于题目原有的概念和表述，也必须充分挖掘其中的关键性质。本题中我们不要用后缀式去直接求解，而是用中缀式，因为后者更方便思考和求解问题。但是这并不意味着我们忽视后缀式及其具有的性质，恰恰想法其具有的性质是解题的关键。

// 贪心——分类讨论——AcWing 1247. 后缀表达式
// 贪心策略：
// M == 0时直接相加输出；
// M != 0时，先加上最大的数和减去最小的数，其余的数加上其绝对值。
// 注意要能挖掘到题目的性质：
// 只要存在至少一个减号，我们就能将任意数量的加号变成减号，
// M != 0 时，减号数量可以为1~N+M中的任意个，且至少有一个加号和减号
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010; 
// 注意数据范围： n <= 10^5 , m <= 10^5 
// 则n + m + 1 <= 2 * 10 ^5 + 1 不要写错了!!

int a[N];

int main(){
    int n, m;
    cin >> n >> m;
    int k = n + m + 1;
    for (int i = 0 ; i < k; ++ i) scanf("%d", &a[i]);

    LL res = 0;
    // 按减号个数分类讨论
    if (!m){
        for (int i = 0; i < k; ++ i)
            res += a[i];
    }
    else{
        sort(a, a + k); // 找到最大值和最小值
        
        res = a[k - 1] - a[0]; 
        // m != 0时至少加上一个数、减去一个数，选最大和最小
        for (int i = 1; i < k - 1; ++ i)
            res += abs(a[i]);
            // 其余直接加上绝对值
    }
    printf("%lld\n", res);
    return 0;
}

峰谷类

1. AcWing 1055. 股票买卖 II

本题我最初做时费了很长时间都没有想到正确思路，究其原因还是做题的方法不对。

首先本题题目说明并不是非常清楚，导致我没有正确理解题意，误认为每一天只能有一次操作（不能当天买卖或卖买），然而题目的只要求在再次购买前出售掉之前的股票，一天内是可以多次操作的。这反映了我在做题时不认真理解，容易乱加约束或少约束的问题。

由于没有正确理解题意，我自然没有发现本题的一个最关键的性质：任何一个跨度大于一的交易都等价于连续跨度为一的多次交易之和（即拆分成连续当天买第二天卖的交易）。由于这个性质，我们就只需关注跨度为一的交易，只要收益为正就可以进行。进行完所有跨度为一的交易，我们即可得到最优解。

发现这种性质的关键是要去思考任意一笔交易能不能进行转化，表示成更小的交易之和（分解成子问题的思想）。

我在分析时没有挖掘题目隐含的性质，而是深陷入对各种复杂约束条件的人为分析中，这并不符合贪心应用简单局部最优策略进行迭代优化的特性。

同时我在思考时受前面做题的影响，过多的局限于排序的策略，并陷入对全局问题的思考，而忽视了对父问题和子问题的迭代关系的思考。盲目试图进行数学推导也是一大问题。

我在思考时，一直局限于思考如何选择买入的时间点和卖出的时间点、买卖的次数应该是多少，这些量显然是无法直接求出的同时也不应该去直接求，我们不应该纠结于如何用数学推导出这些量。贪心的思想恰在于用最简单的局部最优策略去建立一个简单的选择标准，然后迭代地求解而不是直接求解。既然买入卖出的时间点、买卖的次数这些量不确定性太高，不好求，我们就应该思考如何将它们转化，规避直接求解。

另一种想法就是直接去猜想一个最简单粗暴、短视的策略，并证明其可行性。同时可以思考我们方便进行的操作和便于确定的标准是什么，能不能用起来表示问题量。

交易次数可以任意，并不是为了让我们自己确定次数，而是因为此时具有特殊的性质。

// 贪心——峰谷类——AcWing 1055. 股票买卖 II
// 贪心策略：
// 利用任何一个跨度大于一的交易都等价于连续跨度为一的多次交易之和这一性质将交易分解表示
// 对所有收入为正的跨度为一的交易求和
// 分解转化问题，转化为相邻项比较的问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int s[N];

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; ++ i) scanf("%d\n", &s[i]);

    int res = 0;
    for (int i = 0; i < n - 1; ++ i){
        int dt =  s[i+1] - s[i];
        if (dt > 0) res += dt;
        // 对所有收入为正的跨度为一的交易求和
    }
    printf("%d\n", res);
    return 0;
}

分类讨论

分析出问题的性质很关键

维护贪心策略的算法或数据结构

排序

栈

堆

平衡树

双指针

二分

链表

位掩码