网上找的一些算法贪心与随机化

1、贪心法与随机法2011曹文信息学奥林匹克夏令营 江苏省常州高级中学 吴涛 贪心的含义贪心只是一种策略或方法，而不是算法，推进的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪心选择（操作）归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。 贪心法的优势在于编程简单、运行效率高、空间复杂度低等特点。是信息学竞赛中的一个有力武器，受到广大同学们的青睐。牛郎织女鹊桥相会鹊桥相会1一年一度的七夕又要到了，可歌可泣的牛郎织女又可以在鹊桥相会了。大家有没有雅兴坐在葡萄藤下倾听他们的对话？ 我们知道，牛郎要与织女相见，必须要有喜鹊搭桥。所以，牛郎必须在天河岸上等待，直到有喜鹊经过，于是

2、牛郎可以搭乘这只喜鹊往河对岸走。当然，牛郎急着去见织女，所有在途中，如果有速度更快的喜鹊赶上了他，他就会换乘那只速度更快的喜鹊。我们可以假定喜鹊的速度是恒定不变的，并且喜鹊一直是沿直线飞行的(不转弯，更不回头)，牛郎坐上喜鹊所花的时间忽略不计。现给出天河的宽度、每只喜鹊的初始位置(我们设牛郎所在位置为0，天河方向为正方向)以及它们的速度(有可能是负数，代表喜鹊往反方向飞行)，这些数据都是整数。请你来帮忙计算一下牛郎到达对岸与织女相会最少需要多少时间，让他们早些有情人终成眷属。_当然，如果没有喜鹊来搭载牛郎，我们可怜的牛郎就到不了对岸与织女相会了，那我们只好很遗憾的跟牛郎说：“Cant Solv

3、e”，我们祈祷不要发生这样的事情。 鹊桥相会2Input 第一行有两个数据w、n，分别代表天河的宽度(单位:km)和喜鹊的只数(1w1000, 1n10000)。 接下来从第二行到第n+1行每行都有两个数据t、v，分别代表1只喜鹊的初始位置(单位:m)和它的飞行速度(单位:m/s)(-1000t1000, -100v100)。 所有的数据范围都不会超过32位整数的表示范围(用int型数据不会溢出)。 输入以0 0结束。Output 如果牛郎能到达对岸输出他到达对岸所花的总时间(结果精确到秒即可，小数部分舍去)；否则输出“Cant Solve”。 Sample Input 1 10 10 0 S

4、ample Output 1000 鹊桥相会3var min,i,w,n,t,v:longint;begin readln(w,n); while(w0)or(n0) do begin min:=maxlongint; for i:=1 to n do begin readln(t,v); if(t0)and(w*1000-t)div vmin) then min:=(w*1000-t)div v; end; if minmaxlongint then writeln(min) else writeln(Cant Solve); readln(w,n); end;end.买蛋糕【试题描述】 今

5、天是路路的生日，生日蛋糕自然是少不了。路路的朋友们一起去蛋糕店来买蛋糕，可是等一行人到了蛋糕店之后，发现那里是人山人海啊-_-。这下可把店家给急坏了，因为人数过多，需求过大，所以人们要等好长时间才能拿到自己的蛋糕。老板为了最大限度的使每位客人尽快拿到蛋糕，因此他需要安排一个制作顺序，使每位客人的平均等待时间最少（如果制作时间相同的，先来的先做）。这使他发愁了，于是他请你来帮忙安排一个制作顺序，使得每位客人的平均等待时间最少。【输入描述】 输入有两行。第一行是一个整数n，表示有n种蛋糕等待制作。第二行有n个数，第i个数表示第i种蛋糕的制作时间。【输出描述】 输出包括一行，有n个整数，每2个整数间

6、用空格隔开，是蛋糕的制作顺序，每个数即是蛋糕的编号。【输入样例】 21 2 【输出样例】 1 2 【解题提示】 对于100%的数据，n = 1000。 排队打水问题1Description 有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2.tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？Input 第一行n，r (n=500,r=75) 第二行为n个人打水所用的时间Ti (Tiaj then begin temp:=ai; ai:=aj; aj:=temp; end; for i:=1 to r do begin j:=i; s:=0; while j=

7、n do begin s:=s+aj; bj:=s; j:=j+r; end; end; s:=0; for i:=1 to n do s:=s+bi; writeln(s);end.Mixing Milk 混合牛奶1描述牛奶包装是一个如此低利润的生意,所以尽可能低的控制初级产品(牛奶)的价格变的十分重要。请帮助Marry的牛奶制造公司(Merry Milk Makers)以可能的最廉价的方式取得他们所需的牛奶。Marry的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,Marry的牛

8、奶制造公司从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。给出Marry牛奶制造公司的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算Marry的牛奶制造公司所要付出钱的最小值。注意:每天农民生产的牛奶的总数对Marry的牛奶制造公司来说足够的。Mixing Milk 混合牛奶2格式PROGRAM NAME: milkINPUT FORMAT:(file milk.in)第 1 行:二个整数, N 和 M。第一个数值,N,(0= N=2,000,000)是Marry的牛奶制造公司的一天需要牛奶的数量。第二个数值,M,(0= M=5,000)是提供牛奶的农民个数。

9、第 2 到 M+1 行:每行二个整数,Pi 和 Ai。Pi(0= Pi=1,000) 是农民 i 牛奶的价格。Ai(0 = Ai = 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。OUTPUT FORMAT:(file milk.out)单独的一行包含单独的一个整数，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用SAMPLE INPUT100 55 209 403 108 806 30SAMPLE OUTPUT630 NOIP2008P_3排座椅1上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一

10、些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。 请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。NOIP2008P_3排座椅2【输入】 输入文件seat.in的第一行，有5各用空格隔开的整数，分别

11、是M，N，K，L，D（2=N，M=1000，0=KM，0=LN，D=2000）。 接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。 输入数据保证最优方案的唯一性。【输出】 输出文件seat.out共两行。 第一行包含K个整数，a1a2aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、第aK行和第aK+1行之间要开辟通道，其中ai ai+1，每两个整数之间用空格隔开（行尾没有空格）。 第二行包含L个整数，b1b2bk，表示第b1列和b1+1列之间、第b

12、2列和第b2+1列之间、第bL列和第bL+1列之间要开辟通道，其中bix2 then inc(ax2) else inc(ax1) else if x1=x2 then if y1y2 then inc(by2) else inc(by1); end;NOIP2008P_3排座椅4 fillchar(ar,sizeof(ar),0); for i:=1 to k do begin max:=1; for j:=2 to m do if ajamax then max:=j; amax:=0; inc(ar0); arar0:=max; end; NOIP2008P_3排座椅5 for i:=1

13、 to ar0-1 do for j:=i+1 to ar0 do if ariarj then begin t:=ari;ari:=arj;arj:=t;end; for i:=1 to ar0-1 do write(ari, ); writeln(arar0); NOIP2008P_3排座椅6 fillchar(br,sizeof(br),0); for i:=1 to l do begin inc(t); max:=1; for j:=2 to n do if bj=bmax then max:=j; bmax:=0; inc(br0); brbr0:=max; end; NOIP200

14、8P_3排座椅7 for i:=1 to br0-1 do for j:=i+1 to br0 do if bribrj then begin t:=bri;bri:=brj;brj:=t;end; for i:=1 to br0-1 do write(bri, ); writeln(brbr0);end.贪心法总结贪心法是双刃剑贪心法用起来非常舒服，程序设计简单不能随便乱用，有些不满足贪心法要求的就会出错(背包问题)归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。如果贪心不能成功，并且找不到合适的方法，随机化是比赛时的一大法宝。随机化的含义随机化算法是这样一种算法：在算法中使用

15、了随机函数，且随机函数的返回值直接或间接地影响了算法的执行流程或执行结果。1、随机选取会改善算法效率：快速排序2、随机选取不保证得到正确解比如：素数判断、背包问题快速排序（分治思想）分析 设N个元素A1.N，要求按非递减排序。 选择某一个元素X（一般取中间或左边那个），从两头(Ai、Aj)开始逐个与X比较，找到左边不小于它的那个元素Ai和右边大于它的那个元素Aj，则交换Ai与Aj ，然后inc(i)、dec(j)再继续进行，直到ij。 如果leftj 对（left ，j）用上述方法继续进行。 如果Iright 对(I，right)用上述方法继续进行。分析X=A1IJI469715134562原

16、始序列569714134562第一趟796541134562第二趟976541134562第三趟J递归方程Sort(L, J) LJSort(I, R) IRSort(L, R)procedure qsort(L,R:integer);var i,j,m,t :integer;begin t:=aL; i:=L;j:=R; while i=j do begin while do inc(i); while do dec(j); if then begin m:=ai; ai:=aj; aj:=m; inc(i); dec(j); end; end; if iR then ; if Lj the

17、n ;end;aiti=jqsort(I ,R)qsort(L ,j)procedure qsort(L,R:integer);var i,j,m,t :integer;begin x=arandom(l,r);i:=L;j:=R; while i=j do begin while do inc(i); while do dec(j); if then begin m:=ai; ai:=aj; aj:=m; inc(i); dec(j); end; end; if iR then ; if Lj then ;end;aiti=jqsort(I ,R)qsort(L ,j)朴素的判断素数方法对于

18、较小的n，我们可以用“筛数法”判定n是否为素数。对于稍大一点的n，我们可以先求出2,sqrt(n)内的所有素数，再用这些素数试除n。这两种方法都要借助于大数组，如果n足够大，就不再适用了。这时，我们只能用2,3,., sqrt(n)试除n，一旦除尽，n必然是合数，否则为素数。 当遇到较大的素数n时，朴素算法会显得十分慢的。其最坏情况时间复杂度为o(n)。 用随机化判断素数若n是素数，对于a=1,2.n-1，有a(n-1)1 (mod n)。所以，若存在整数a1,n-1，使得a(n-1)1 (mod n)，则a必为合数。我们考虑以下算法： ISPRIME_R(n, s:int); i,a:int

19、; for i=1 to s do a=random(1,n-1); if a(n-1) mod n1 then return false; return true; 随机化判断素数的分析这个算法会产生一种错误，即选取的s个a值均满足a(n-1)1 (mod n)，而n是合数时，算法会认为n是合数的证据不足，判其为素数。但当s50时，此算法的正确率就可以到达99%以上。选取适当的s，此算法的时间效率远高于朴素的判定方法。NOIP2001P_4装箱问题问题描述有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。样例输入：24 一个整数，表示箱子容量6 一个整数，表示有n个物品8 接下来n行，分别表示这n 个物品的各自体积312797输出：0一个整数，表示箱子剩余空间。0-1背包问题一个旅行者有一个最多能装m公斤物品的背包，现在又n件物品，它们的重