贪心算法与区间问题

这次跟前一篇文章一样，也是三道题，都是关于区间相交问题的。所谓区间问题，就是一个覆盖范围，那么要在一定条件下保证覆盖范围不重叠，这也是一个很有意思的问题。

贪心算法与背包问题

今天这篇是关于贪心算法的，首先大家会认为这是一个很普通很简单的算法，因为贪心的例子几乎无处不在。确实是这样，但是如果有很多的条件，就会使逻辑复杂，容易让人不知道怎么贪，所以同意我希望通过这几篇的学习我能获得提高，来看我博客的人也是一样。总体的思想框架我全部是按照《算法竞赛入门经典》这本书来搭建的，也算是对上面提出的各个问题的细致研究的报告吧。

那么这篇要来介绍的就是贪心算法的第一个大方向的应用——简单背包问题。有些ACMer接触过背包几乎都是在DP问题，0/1背包、多重背包、超大背包这种的，但是今天要讲的没有这么多的限制条件，背包问题的起源吧并不是在DP而是贪心，就连DP下的背包个人认为除去一些状态判断后还是基于贪心思想的。

好的，那开始我们今天的一连串的背包吧！

今天我们来接触一个有趣的几何问题，主角是一群蚂蚁

循环日程表问题

循环日程表问题。n=2k个运动员进行网球循环赛，需要设计比赛日程表。每个选手必须与其他n−1个选手各赛一次；每个选手一天只能赛一次；循环赛一共进行n−1天。按此要求设计一张比赛日程表，该表有n行和n−1列，第i行j列为第i个选手第j天遇到的选手。

今天要描述的问题叫做棋盘覆盖问题，这个问题可以很好的利用分治思想解决。

溢出漏洞

这篇文章就来聊一聊关于归并排序与二分查找的溢出漏洞。这个漏洞并没有多么神奇，其实很好理解，可能由于是所有人都没往这方面想，所以20多年都没被发现。

二分查找

由于后面会有一些使用二分思想的比较灵活的题目，所以我先来写一下二分查找。

首先，二分查找是一个非常基础的算法，也是而二分思想的基础，所以，全面与透彻的了解是非常有必要的。

比特币节点

• 每个比特币钱包都是一个节点
• 全节点：拥有完整账本，负责转账交易广播和验证
• 轻节点：不挖矿，只交易
• 挖矿节点：增加挖矿功能的全节点，记账节点
• 目前500多万节点，全节点只有1万多

区块链的起源思想

• 去中心化其实是弱中心化
• P2P:peer-to-peer,person-to-person

上一篇文章中提到了关于如何使用归并排序求出逆序对的问题，现在是时候揭晓答案了。

其实非常简单，只需要对前面的归并排序添加一个变量，一行代码就可以了，非常的神奇，那么我们来探究一下到底在哪添加代码能快速求出逆序对呢。