1、概述

贪心算法讲起来容易，就是问题求解的每一步，都用一个局部最佳的策略，如果能够证明局部最佳的策略最终能够保证全局最佳，则可以用贪心算法。

在实际 CSPJ 比赛中，我们不用严谨的求解和证明，只需要尝试做一些反例，如果反例中找不到问题，就可以先用贪心求解。毕竟比赛中时间的权重因素比较高。

在教学中，我们先通过简单的题目让学生理解贪心的概念。之后就可以逐步增加难度，让学生意识到，写出贪心可能容易，但是想到贪心这种解法在比赛中并不那么显而易见。

贪心通常伴随着排序，所以对 STL 的 sort 以及 priority_queue 的熟练应用也是快速解决贪心题目的必备基础，在学习相关题目的时候，可以重点加强巩固相关知识点。

2、sort 函数

sort 函数内部使用快速排序实现，时间复杂度为 O(N*log(N))。对于数据规模为 10 万左右的题目，出题人有可能是希望你用这个时间复杂度来解题的，所以可以留意一下是否需要排序。

对于普通类型，STL 自带了 greater<T>和less<T> 两个比较器，以下是相关代码：

1
2

int v[100];
sort(v, v+n, greater<int>);

sort 函数通常和自定义的结构体排序搭配使用，以下是相关代码：

1
2
3
4
5
6
7
8
9
10
11

struct Person {
    int idx;
    int v;
};
bool operator < (Person a, Person b) {
    return a.v < b.v;
}

Person v[1100];
// 使用时直接用 sort
sort(v, v+n);

sort 函数除了可以像上面这样通过调用 < 符号来比较大小，也可以传入一个比较函数。如下所示：

1
2
3
4
5
6
7
8
9
10
11

struct Person {
    int idx;
    int v;
};
bool comp(Person a, Person b) {
    return a.v < b.v;
}

Person v[1100];
// 使用时直接用 sort
sort(v, v+n, comp);

以下是练习结构体排序的题目：

3、教学题目

推荐的教学题目如下：

1
2

int v[100];
sort(v, v+n, greater<int>);

1
2
3
4
5
6
7
8
9
10
11

struct Person {
    int idx;
    int v;
};
bool operator < (Person a, Person b) {
    return a.v < b.v;
}

Person v[1100];
// 使用时直接用 sort
sort(v, v+n);

1
2
3
4
5
6
7
8
9
10
11

struct Person {
    int idx;
    int v;
};
bool comp(Person a, Person b) {
    return a.v < b.v;
}

Person v[1100];
// 使用时直接用 sort
sort(v, v+n, comp);