1、概述贪心算法讲起来容易,就是问题求解的每一步,都用一个局部最佳的策略,如果能够证明局部最佳的策略最终能够保证全局最佳,则可以用贪心算法。在实际 CSPJ 比赛中,我们不用严谨的求解和证明,只需要尝试做一些反例,如果反例中找不到问题,就可以先用贪心求解。毕竟比赛中时间的权重因素比较高。在教学中,我们先通过简单的题目让学生理解贪心的概念。之后就可以逐步增加难度,让学生意识到,写出贪心可能容易,但是想到贪心这种解法在比赛中并不那么显而易见。贪心通常伴随着排序,所以对 STL 的sort以及priority_queue的熟练应用也是快速解决贪心题目的必备基础,在学习相关题目的时候,可以重点加强巩固相关知识点。2、sort 函数sort 函数内部使用快速排序实现,时间复杂度为O(N*log(N))。对于数据规模为 10 万左右的题目,出题人有可能是希望你用这个时间复杂度来解题的,所以可以留意一下是否需要排序。对于普通类型,STL 自带了greater和less两个比较器,以下是相关代码:intv[100];sort(v, v+n, greater);sort 函数通常和自定义的结构体排序搭配使用,以下是相关代码:structPerson{intidx;intv;};booloperator< (Person a, Person b) {returna.v <
...
继续阅读
(4)