[Day.1]贪心算法

目录

背景：

正文：

贪心算法能解决的问题：

思路：

那如果我们要知道可以参加哪些活动怎么办/p>

Love is worth years.爱可抵岁月漫长。

背景：

作为一名刚转专业到软件工程的菜鸡小白，只是简单的知道一些基础的c语言的编程语言，第一次听到ACM，然后抱着试一试的求虐心态就参加了校内举办的ACM的选拔赛，3个小时！!一共九道题，我就做出了一道！！没接触过算法的我，通过一个安排活动问题第一次听说了贪心算法，这个名词，而且有好多做出来两道的同学就是做出来的，我做的最简单的那道和贪心算法的那道题。所以我决定今天开始我的算法学习之路！！！！先从贪心算法开始！

正文：

贪心算法：贪心贪心，就是贪，从来不从全局考虑而是做当前最好的选择！当然一个个当前最好的选择可能就构成了最完美的整体最优解。比如你找女朋友，要是每次都考虑钱，钱省下来了，但女朋友没了。所以=。=贪心算法不是万能的他只能解决一些特定的问题。

贪心算法能解决的问题：

1.背包问题

2.活动时间安排的问题（我不会的那个题今天先重点研究这个）区间 问题

3.线段覆盖问题（lines cover)

4.数字组合问题

5.最小生成树（克鲁斯卡尔算法）

思路：

好好好，算法贪心我可不能贪心先用c活动时间问题解决！

假设某同学某一天要参加n个活动 E = {1, 2, 3 … n}，其每个活动 i 都有起始时间 si 和结束时间 fi, 且有 si < fi。若区间（si，fi）和（sj，fj）不相交，则称活动 i 与活动 j 是相容的。现在给定 n 个活动的开始时间和结束时间，请设计一个活动安排方案，使得参加的活动数目最多。

下面是代码：

思路：建立sort函数利用其先对结束时间进行排序。

排完序以后哩就要进行“贪心”了！！ 下面是关于贪心算法的代码：

完整代码如下：

这样我们就可以知道小明能参加多少二课活动了！！！

那如果我们要知道可以参加哪些活动怎么办/strong>

可以用一个计数数组跟着它的变化而变化如下代码：

Love is worth years./s>
热爱可抵岁月漫长。