網(wǎng)上找的一些算法貪心與隨機(jī)化

1、貪心法與隨機(jī)法2011曹文信息學(xué)奧林匹克夏令營(yíng) 江蘇省常州高級(jí)中學(xué) 吳濤 貪心的含義貪心只是一種策略或方法，而不是算法，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪心選擇（操作）歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。 貪心法的優(yōu)勢(shì)在于編程簡(jiǎn)單、運(yùn)行效率高、空間復(fù)雜度低等特點(diǎn)。是信息學(xué)競(jìng)賽中的一個(gè)有力武器，受到廣大同學(xué)們的青睞。牛郎織女鵲橋相會(huì)鵲橋相會(huì)1一年一度的七夕又要到了，可歌可泣的牛郎織女又可以在鵲橋相會(huì)了。大家有沒有雅興坐在葡萄藤下傾聽他們的對(duì)話？ 我們知道，牛郎要與織女相見，必須要有喜鵲搭橋。所以，牛郎必須在天河岸上等待，直到有喜鵲經(jīng)過，于是

2、牛郎可以搭乘這只喜鵲往河對(duì)岸走。當(dāng)然，牛郎急著去見織女，所有在途中，如果有速度更快的喜鵲趕上了他，他就會(huì)換乘那只速度更快的喜鵲。我們可以假定喜鵲的速度是恒定不變的，并且喜鵲一直是沿直線飛行的(不轉(zhuǎn)彎，更不回頭)，牛郎坐上喜鵲所花的時(shí)間忽略不計(jì)。現(xiàn)給出天河的寬度、每只喜鵲的初始位置(我們?cè)O(shè)牛郎所在位置為0，天河方向?yàn)檎较?以及它們的速度(有可能是負(fù)數(shù)，代表喜鵲往反方向飛行)，這些數(shù)據(jù)都是整數(shù)。請(qǐng)你來幫忙計(jì)算一下牛郎到達(dá)對(duì)岸與織女相會(huì)最少需要多少時(shí)間，讓他們?cè)缧┯星槿私K成眷屬。_當(dāng)然，如果沒有喜鵲來搭載牛郎，我們可憐的牛郎就到不了對(duì)岸與織女相會(huì)了，那我們只好很遺憾的跟牛郎說：“Cant Solv

3、e”，我們祈禱不要發(fā)生這樣的事情。 鵲橋相會(huì)2Input 第一行有兩個(gè)數(shù)據(jù)w、n，分別代表天河的寬度(單位:km)和喜鵲的只數(shù)(1w1000, 1n10000)。 接下來從第二行到第n+1行每行都有兩個(gè)數(shù)據(jù)t、v，分別代表1只喜鵲的初始位置(單位:m)和它的飛行速度(單位:m/s)(-1000t1000, -100v100)。 所有的數(shù)據(jù)范圍都不會(huì)超過32位整數(shù)的表示范圍(用int型數(shù)據(jù)不會(huì)溢出)。 輸入以0 0結(jié)束。Output 如果牛郎能到達(dá)對(duì)岸輸出他到達(dá)對(duì)岸所花的總時(shí)間(結(jié)果精確到秒即可，小數(shù)部分舍去)；否則輸出“Cant Solve”。 Sample Input 1 10 10 0 S

4、ample Output 1000 鵲橋相會(huì)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、天是路路的生日，生日蛋糕自然是少不了。路路的朋友們一起去蛋糕店來買蛋糕，可是等一行人到了蛋糕店之后，發(fā)現(xiàn)那里是人山人海啊-_-。這下可把店家給急壞了，因?yàn)槿藬?shù)過多，需求過大，所以人們要等好長(zhǎng)時(shí)間才能拿到自己的蛋糕。老板為了最大限度的使每位客人盡快拿到蛋糕，因此他需要安排一個(gè)制作順序，使每位客人的平均等待時(shí)間最少（如果制作時(shí)間相同的，先來的先做）。這使他發(fā)愁了，于是他請(qǐng)你來幫忙安排一個(gè)制作順序，使得每位客人的平均等待時(shí)間最少。【輸入描述】 輸入有兩行。第一行是一個(gè)整數(shù)n，表示有n種蛋糕等待制作。第二行有n個(gè)數(shù)，第i個(gè)數(shù)表示第i種蛋糕的制作時(shí)間?！据敵雒枋觥?輸出包括一行，有n個(gè)整數(shù)，每2個(gè)整數(shù)間

6、用空格隔開，是蛋糕的制作順序，每個(gè)數(shù)即是蛋糕的編號(hào)?！据斎霕永?21 2 【輸出樣例】 1 2 【解題提示】 對(duì)于100%的數(shù)據(jù)，n = 1000。 排隊(duì)打水問題1Description 有n個(gè)人排隊(duì)到r個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間t1、t2.tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費(fèi)的時(shí)間最少？Input 第一行n，r (n=500,r=75) 第二行為n個(gè)人打水所用的時(shí)間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描述牛奶包裝是一個(gè)如此低利潤(rùn)的生意,所以盡可能低的控制初級(jí)產(chǎn)品(牛奶)的價(jià)格變的十分重要。請(qǐng)幫助Marry的牛奶制造公司(Merry Milk Makers)以可能的最廉價(jià)的方式取得他們所需的牛奶。Marry的牛奶制造公司從一些農(nóng)民那購買牛奶，每個(gè)農(nóng)民賣給牛奶制造公司的價(jià)格不一定相同。而且,如一只母牛一天只能生產(chǎn)一定量的牛奶,農(nóng)民每一天只有一定量的牛奶可以賣。每天,Marry的牛

8、奶制造公司從每個(gè)農(nóng)民那購買一定量的牛奶,少于或等于農(nóng)民所能提供的最大值。給出Marry牛奶制造公司的每日的牛奶需求,連同每個(gè)農(nóng)民的可提供的牛奶量和每加侖的價(jià)格,請(qǐng)計(jì)算Marry的牛奶制造公司所要付出錢的最小值。注意:每天農(nóng)民生產(chǎn)的牛奶的總數(shù)對(duì)Marry的牛奶制造公司來說足夠的。Mixing Milk 混合牛奶2格式PROGRAM NAME: milkINPUT FORMAT:(file milk.in)第 1 行:二個(gè)整數(shù), N 和 M。第一個(gè)數(shù)值,N,(0= N=2,000,000)是Marry的牛奶制造公司的一天需要牛奶的數(shù)量。第二個(gè)數(shù)值,M,(0= M=5,000)是提供牛奶的農(nóng)民個(gè)數(shù)。

9、第 2 到 M+1 行:每行二個(gè)整數(shù),Pi 和 Ai。Pi(0= Pi=1,000) 是農(nóng)民 i 牛奶的價(jià)格。Ai(0 = Ai = 2,000,000)是農(nóng)民 i 一天能賣給Marry的牛奶制造公司的牛奶數(shù)量。OUTPUT FORMAT:(file milk.out)單獨(dú)的一行包含單獨(dú)的一個(gè)整數(shù)，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小費(fèi)用SAMPLE INPUT100 55 209 403 108 806 30SAMPLE OUTPUT630 NOIP2008P_3排座椅1上課的時(shí)候總有一些同學(xué)和前后左右的人交頭接耳，這是令小學(xué)班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一

10、些有趣的現(xiàn)象，當(dāng)同學(xué)們的座次確定下來之后，只有有限的D對(duì)同學(xué)上課時(shí)會(huì)交頭接耳。同學(xué)們?cè)诮淌抑凶闪薓行N列，坐在第i行第j列的同學(xué)的位置是（i，j），為了方便同學(xué)們進(jìn)出，在教室中設(shè)置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個(gè)辦法，或許可以減少上課時(shí)學(xué)生交頭接耳的問題：她打算重新擺放桌椅，改變同學(xué)們桌椅間通道的位置，因?yàn)槿绻粭l通道隔開了兩個(gè)會(huì)交頭接耳的同學(xué)，那么他們就不會(huì)交頭接耳了。 請(qǐng)你幫忙給小雪編寫一個(gè)程序，給出最好的通道劃分方案。在該方案下，上課時(shí)交頭接耳的學(xué)生對(duì)數(shù)最少。NOIP2008P_3排座椅2【輸入】 輸入文件seat.in的第一行，有5各用空格隔開的整數(shù)，分別

11、是M，N，K，L，D（2=N，M=1000，0=KM，0=LN，D=2000）。 接下來D行，每行有4個(gè)用空格隔開的整數(shù)，第i行的4個(gè)整數(shù)Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個(gè)同學(xué)會(huì)交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。 輸入數(shù)據(jù)保證最優(yōu)方案的唯一性?！据敵觥?輸出文件seat.out共兩行。 第一行包含K個(gè)整數(shù)，a1a2aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、第aK行和第aK+1行之間要開辟通道，其中ai ai+1，每?jī)蓚€(gè)整數(shù)之間用空格隔開（行尾沒有空格）。 第二行包含L個(gè)整數(shù)，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.貪心法總結(jié)貪心法是雙刃劍貪心法用起來非常舒服，程序設(shè)計(jì)簡(jiǎn)單不能隨便亂用，有些不滿足貪心法要求的就會(huì)出錯(cuò)(背包問題)歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。如果貪心不能成功，并且找不到合適的方法，隨機(jī)化是比賽時(shí)的一大法寶。隨機(jī)化的含義隨機(jī)化算法是這樣一種算法：在算法中使用

15、了隨機(jī)函數(shù)，且隨機(jī)函數(shù)的返回值直接或間接地影響了算法的執(zhí)行流程或執(zhí)行結(jié)果。1、隨機(jī)選取會(huì)改善算法效率：快速排序2、隨機(jī)選取不保證得到正確解比如：素?cái)?shù)判斷、背包問題快速排序（分治思想）分析 設(shè)N個(gè)元素A1.N，要求按非遞減排序。 選擇某一個(gè)元素X（一般取中間或左邊那個(gè)），從兩頭(Ai、Aj)開始逐個(gè)與X比較，找到左邊不小于它的那個(gè)元素Ai和右邊大于它的那個(gè)元素Aj，則交換Ai與Aj ，然后inc(i)、dec(j)再繼續(xù)進(jìn)行，直到ij。 如果leftj 對(duì)（left ，j）用上述方法繼續(xù)進(jìn)行。 如果Iright 對(duì)(I，right)用上述方法繼續(xù)進(jìn)行。分析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)樸素的判斷素?cái)?shù)方法對(duì)于

18、較小的n，我們可以用“篩數(shù)法”判定n是否為素?cái)?shù)。對(duì)于稍大一點(diǎn)的n，我們可以先求出2,sqrt(n)內(nèi)的所有素?cái)?shù)，再用這些素?cái)?shù)試除n。這兩種方法都要借助于大數(shù)組，如果n足夠大，就不再適用了。這時(shí)，我們只能用2,3,., sqrt(n)試除n，一旦除盡，n必然是合數(shù)，否則為素?cái)?shù)。 當(dāng)遇到較大的素?cái)?shù)n時(shí)，樸素算法會(huì)顯得十分慢的。其最壞情況時(shí)間復(fù)雜度為o(n)。 用隨機(jī)化判斷素?cái)?shù)若n是素?cái)?shù)，對(duì)于a=1,2.n-1，有a(n-1)1 (mod n)。所以，若存在整數(shù)a1,n-1，使得a(n-1)1 (mod n)，則a必為合數(shù)。我們考慮以下算法： 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; 隨機(jī)化判斷素?cái)?shù)的分析這個(gè)算法會(huì)產(chǎn)生一種錯(cuò)誤，即選取的s個(gè)a值均滿足a(n-1)1 (mod n)，而n是合數(shù)時(shí)，算法會(huì)認(rèn)為n是合數(shù)的證據(jù)不足，判其為素?cái)?shù)。但當(dāng)s50時(shí)，此算法的正確率就可以到達(dá)99%以上。選取適當(dāng)?shù)膕，此算法的時(shí)間效率遠(yuǎn)高于樸素的判定方法。NOIP2001P_4裝箱問題問題描述有一個(gè)箱子容量為V（正整數(shù)，0V20000），同時(shí)有n個(gè)物品（0n30，每個(gè)物品有一個(gè)體積（正整數(shù)）。要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。樣例輸入：24 一個(gè)整數(shù)，表示箱子容量6 一個(gè)整數(shù)，表示有n個(gè)物品8 接下來n行，分別表示這n 個(gè)物品的各自體積312797輸出：0一個(gè)整數(shù)，表示箱子剩余空間。0-1背包問題一個(gè)旅行者有一個(gè)最多能裝m公斤物品的背包，現(xiàn)在又n件物品，它們的重