二分查找

所谓二分查找,就是在有序的数组中查找某一值的元素,基本方法是分治

不保证Key(所查找的关键字)在集合中的查找

例如:最长不下降子序列中的二分查找,当动规到某一位置时,要知道在辅助数组中Key的位置,需要找到Key所在位置或仅比Key小的(\(\)c[i]\leqslant key

CODE:

这样写好像很简单

P156 吞噬比赛 NlogN最长不下降子序列

MY CODE:

Continue reading “P156 吞噬比赛 NlogN最长不下降子序列”

SPFA

算法简介

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法,现在广为流传的Bellman-Ford算法实际上是山寨版。

算法流程

算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。

这个算法,简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
Continue reading “SPFA”

[转]多关键字的快速排序

{

作者:时光9154

当然底下的C代码是我(Comzyh)写的

http://hi.baidu.com/time9154

}

多关键字的快速排序

解决类似如下的问题:输入n组坐标(xi,yi),要求按xi的升序排序后,对于xi=xj(j>i),yi~j升序排列

即双关键字排序,先保证第一关键字的升序,在第一关键字一样的情况下保证第二关键字的升序
Continue reading “[转]多关键字的快速排序”