荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 三个经典的贪心算法 zz
发信站: 荔园晨风BBS站 (Tue Oct 16 11:28:24 2007), 站内
有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学。有人说贪心
算法是最复杂的算法，原因也很简单：这世上贪的人太多了，那轮到你我的份？
不论难度如何，贪心算法都是一个很重要的算法，我在网上N多Online Judge中的题
目中，总结了三类较为常见，也十分经典的贪心算法，发布在这儿Just For Fun。
（注：由于没有现成的名字可用，这三种类型贪心算法的名字都是我自己取的，如
果你听着别扭，请见谅。）
No 1.线段覆盖（linescover）
题目大意：
在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖
了多大的长度。
解题思路：
将线段按其坐标进行排序（排序的具体方法:按起始坐标排，起始坐标相同的按终
止坐标排，都是小在前大在后）,使之依次递增，并按顺序分别编号为X(i),X(i).a代表其起
始坐标，X(i).b代表其终止坐标。
定义一个变量last记录考虑到当前线段之时被线段覆盖的最大的坐标值，再定义一
个变量length记录当前线段覆盖的长度。对于后面的线段，我们把它看成由两个部分组成，
即把它分成last之前的线段和last之后的线段。（如果线段全部处在last之后，其last之前
的部分不存在。）由于我们排过序，我们可以肯定当前考虑的线段X(i)其处在last之前的部
分不会对length造成影响（因为X(i-1).b=last，X(i).a>= X(i-1).a,即X(i)在last之前的
部分所处位置肯定被线段X(i-1)覆盖过），所以会对length产生影响的即是X(i)处在last之
后的部分。
所以我们可以依次对每条线段做如下处理：（初始化length为零，last为负无穷）
length+=X(i).b-last (X(i).a<=last 且 X(i).b>=last)
length+=X(i).b-X(i).a (X(i).a>last)
last=X(i).b;
最后length就为我们所需要的答案。
No 2.最优数对（bestpair）
题目大意：
按递增的顺序告诉你N个正整数和一个实数P，要求求出求出该数列中的比例最接近
P的两个数（保证绝对没有两个数使得其比值为P）。
解题思路：
定义两个指针i和j，先初始化i=j=1，然后进行如下操作：
当code[j]/code[i]>p时，inc（j）；
当code[j]/code[i]<p时，inc（i）。
记录其中产生的最优值即为答案。
No 3.连续数之和最大值（maxsum）
题目大意：
给出一个长度为N的数列（数列中至少有一个正数），要求求出其中的连续数之和的
最大值。（也可以加入a和b来限制连续数的长度不小于a且不大于b）。
解题思路：
先说不加限制的那种，定义一个统计变量tot，然后用循环进行如下操作：inc（
tot，item） 其中如果出现tot<0的情况，则将tot赋值为0。在循环过程之中tot出现的最大
值即为答案。
如果加入了限制条件的话，问题就变得难一些了（这句真的不是废话）。为此我们
先定义数组sum[i]来表示code[1]到code[i]之和（这样的话code[a]~code[b]的和我们就可
以用sum[b]-sum[a-1]来表示了。）。
再维护一个数组hash[i]来表示满足条件的sum[a-1]的下标，并使之按递增顺序排列
，这样当前以第i的数为终止的数列的最大值肯定就是sum[i]-sum[hash[1]]。
现在我们来讨论hash数组之中的数据需要满足的条件和如何维护的具体问题：
当考虑到以第i个数为结尾时，hash[i]所表示的下标需要满足的第一个条件就是题
目规定的长度限制，我们需要实时的加入满足长度规定的下标，删除不符合要求的下标。其
次，与不加限制条件时相同，若sum[i]-sum[hash[1]]的值小于零，则清空数组hash。
维护时可以这样，当考虑到第i个数时，我们就将下标i-a+1加入到hash中，因为
hash中原来已经排好序，因此我们我们可以用插入排序来维护 hash的递增性，然后我们考
察hash[1]，若hash[1]<i-b+1，则证明其已超出长度限制，我们就将其删除，接着再考虑更
新后的 hash[1],如此重复直至找到一个满足条件的hash[1]为止。
我们可以用链表来表示hash，这样就可以减少数据加入和删除时频繁数据移动的时
间消耗。
记录下sum[i]-sum[hash[1]]的最大值即为答案。
--
Science is what we understand well enough to explain to a computer.
Art is everything else we do.
———— Donald E. Knuth
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.224]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店