貪心與隨機(jī)和法

1、http:/JudgeOnline/showproblem?problem_id=1060鵲橋相會(huì)Time Limit:1000MSMemory Limit:65536KTotal Submit:178 Accepted:37Description一年一度的七夕又要到了，可歌可泣的織女又可以在鵲橋相會(huì)了。不知道大家有沒(méi)有雅興陪redraiment 坐在葡萄藤下他們的。知道所以要與織女相見(jiàn)，必須要有喜鵲搭橋。必須在天河岸上等待，直到有喜鵲經(jīng)過(guò)，于是可以搭乘這只喜鵲往河對(duì)岸走。當(dāng)然，牛著去見(jiàn)織女，所有在途中，如果有速度更快的喜鵲趕上了他，他就會(huì)換乘那只速度更快的喜鵲。可以假定喜鵲的速度是恒定不變的

2、，并且喜鵲一直是沿直線飛行的(不轉(zhuǎn)彎，更不回頭)，坐上喜鵲所花的時(shí)間忽略不計(jì)?，F(xiàn)給出天河的寬度、每只喜鵲的初始位置(所在位置為 0，天河方向?yàn)樵O(shè)正方向)以及它們的速度(有可能是負(fù)數(shù)，代表喜鵲往反方向飛行)，這些數(shù)據(jù)都是整數(shù)。請(qǐng)你來(lái)幫忙計(jì)算一下早些有終成眷屬。_到達(dá)對(duì)岸與織女相會(huì)最少需要多少時(shí)間，讓他們當(dāng)然，如果沒(méi)有喜鵲來(lái)搭載，的就到不了對(duì)岸與織女相會(huì)了，祈禱不要發(fā)生這樣的事情。只好很遺憾的跟說(shuō)：“Cant Solve”，那Input第一行有兩個(gè)數(shù)據(jù)w、n，分別代表天河的寬度( 1n10000)。:km)和喜鵲的只數(shù)(1w1000,接下來(lái)從第二行到第n+1 行每行都有兩個(gè)數(shù)據(jù) t、v，分別代表

3、1 只喜鵲的初始位置(:m)和它的飛行速度(:m/s)(-1000t1000, -100v100)。所有的數(shù)據(jù)范圍都不會(huì)超過(guò) 32 位整數(shù)的表示范圍(用型數(shù)據(jù)不會(huì)溢出)。輸入以 0 0 結(jié)束。Output如果能到達(dá)對(duì)岸輸出他到達(dá)對(duì)岸所花的總時(shí)間(結(jié)果精確到秒即可，小數(shù)部分舍去)；否則輸出“Cant Solve”。Sle Input100110Sle Output1000varmin,i,w,n,t,v:long; beginreadln(w,n); while(w0)or(n0) dobeginmin:=maxlong; for i:=1 to n dobeginreadln(t,v); if

4、(t0)and(w*1000-t)div then min:=(w*1000-t)div v;end;vmin)if mthen elseaxlongwriwrin(min)n(Cant Solve);readln(w,n);end;end.ht/Problem_Show.as=10972004T 合并果子（fruit.pas/dpr/p）【問(wèn)題描述】在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來(lái)，而且按果子的不同種類(lèi)分成了不同的堆。多多決定把所有的果子一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過(guò) n-1 次合并之后，就只剩下一堆了。多

5、多在合并果子時(shí)總共消耗的體力等于每次合并所消耗體力之和。因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為 1，并且已知果子的種類(lèi)數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。例3 種果子，數(shù)目依次為 1，2，9?？梢韵葘?1、2 堆合并，新堆數(shù)目為 3，耗費(fèi)體力為 3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 12，耗費(fèi)體力為 12。所以多多總共耗費(fèi)體力=3+12=15?？梢宰C明 15 為最小的體力耗費(fèi)值?！据斎胛募枯斎胛募ruit.in 包括兩行，第一行是一個(gè)整數(shù) n(1=n

6、=10000),表示果子的種類(lèi)數(shù)。第二行包含n 個(gè)整數(shù)，用空格分隔，第i 個(gè) ai(1=ai=20000)是第 i 個(gè)果子的數(shù)目?！据敵鑫募枯敵鑫募?fruit.out 包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于 231?！緲永斎搿?1 2 9【樣例輸出】15【數(shù)據(jù)規(guī)?！繉?duì)于 30%的數(shù)據(jù)，保證有 n=1000;對(duì)于 50%的數(shù)據(jù)，保證有 n=5000;對(duì)于全部的數(shù)據(jù)，保證有 n=10000?！救腴T(mén)】買(mǎi)蛋糕 II時(shí)間限制：1000MS內(nèi)存限制：1000K解答次數(shù)：51 通過(guò)次數(shù)：11【試題描述】今天是路路的生日，生日蛋糕自然是少不了。路路的朋友們一起去蛋

7、糕店來(lái)買(mǎi)蛋糕，等一行人到了蛋糕店之后，發(fā)現(xiàn)那里是人山人海啊-_-。這下可把店家給急壞了，因?yàn)槿藬?shù)過(guò)多，需求過(guò)大，所以人們要等好長(zhǎng)時(shí)間才能拿到自己的蛋糕。為了最大限度的使每位客人盡快拿到蛋糕，因此他需要安排一個(gè)制作順序，使每位客人的平均等待時(shí)間最少（如果制作時(shí)間相同的，先來(lái)的先做）。這使他發(fā)愁了，于是他請(qǐng)你來(lái)幫忙安排一個(gè)制作順序，使得每位客人的平均等待時(shí)間最少?！据斎朊枋觥枯斎胗袃尚?。第一行是一個(gè)整數(shù) n，表示有 n 種蛋糕等待制作。第二行有 n 個(gè)數(shù)，第i 個(gè)數(shù)表示第 i 種蛋糕的制作時(shí)間。【輸出描述】輸出包括一行，有 n 個(gè)整數(shù)，每 2 個(gè)整數(shù)間用空格隔開(kāi)，是蛋糕的制作順序，每個(gè)數(shù)即是蛋糕的

8、?！据斎霕永?1 2【輸出樣例】1 2【解題提示】對(duì)于 100%的數(shù)據(jù)，n = 1000。htt:8080/BS41Online/showproblem?problem_id=1002【培訓(xùn)試題】排隊(duì)打水問(wèn)題(normal)Time Limit:1000MSMemory Limit:65536KTotal Submit:934 Accepted:325Description有n 個(gè)人排隊(duì)到 r 個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間t1、t2tn 為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費(fèi)的時(shí)間最少？Input第一行n，r (n=500,r=75)第二行為n 個(gè)人打水所用的時(shí)間

9、Ti (Tiajthen begemp:=ai;ai:=aj;aj:=temp;end;for i:=1 to rdobeginj:=i;s:=0;while j=n dobegins:=s+aj;bj:=s;j:=j+r;end;end;s:=0;for i:=1 ton dos:=s+bi;wrin(s);end.5Mixing Milk 混合牛奶描述牛奶包裝是一個(gè)如此低利潤(rùn)的生意,所以盡可能低的控制初級(jí)產(chǎn)品(牛奶)的價(jià)格變的十分重要。請(qǐng)幫助 Marry 的牛奶制造公司(Merry Milk Makers)以可能的最廉價(jià)的方式取得他們所需的牛奶。Marry 的牛奶制造公司從一些農(nóng)民那牛奶，

10、每個(gè)農(nóng)民賣(mài)給牛奶制造公司的價(jià)格不一定相同。而且,如一只母牛一天只能生產(chǎn)一定量的牛奶,農(nóng)民每一天只有一定量的牛奶可以賣(mài)。每天,Marry 的牛奶制造公司從每個(gè)農(nóng)民那出 Marry 牛奶制造公司的一定量的牛奶,少于或等于農(nóng)民所能提供的最大值。給的牛奶需求,連同每個(gè)農(nóng)民的可提供的牛奶量和每的價(jià)格,請(qǐng)計(jì)算 Marry 的牛奶制造公司所要付出錢(qián)的最小值。注意:每天農(nóng)民生產(chǎn)的牛奶的總數(shù)對(duì) Marry 的牛奶制造公司來(lái)說(shuō)足夠的。格式PROGRAM NAME: milkINPUT FORMAT:(file milk.in)第 1 行:二個(gè)整數(shù),N 和 M。第一個(gè)數(shù)值,N,(0=數(shù)量。N=2,000,000)是

11、 Marry 的牛奶制造公司的一天需要牛奶的第二個(gè)數(shù)值,M,(0=M=5,000)是提供牛奶的農(nóng)民個(gè)數(shù)。第 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 一天能賣(mài)給 Marry 的牛奶制造公司的牛奶數(shù)量。OUTPUT FORMAT:(file milk.out)單獨(dú)的一行包含單獨(dú)的一個(gè)整數(shù)，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小費(fèi)用SLE INPUT100 5593862040108030SLE OUTPUT630代碼：ID:jzkkwei1 PROG: mil

12、k LANG: PASCALprogram milk; varcost:64;i,j,temp,n,m:long p:array1.5000of a:array1.5000of;long long;procedure varc:long beginc:=a;a:=b;b:=c; end; procedure varswap(var a,b:long);sort(lx,rx:long);i,j,x:long; begini:=lx;j:=rx; x:=prandom(j-i+1)+i; repeatwhile (pix)dec(j);dodoif ij;if ilx then sort(lx,j

13、);end; beginrandomize; assign(input,milk.in);reset(input); assign(output,milk.out);rewrite(output); readln(n,m);for i:= 1 to m doreadln(pi,ai);sort(1,m);i:=1;cost:=0; while n0 dobeginif ai=0 then inc(i); if n-ai=0 thenbeginn:=n-ai;temp:=ai*pi;ai:=0;endelsebegintemp:=n*pi; n:=0;end; cost:=cost+temp;e

14、nd; n(cost);wriclose(input); close(output);end.ht排座椅1 排座椅/Problem_Show.as=1498（seat.pas/【問(wèn)題描述】p）上課的時(shí)候總有一些同學(xué)和前后左右的人交頭接耳，這是令小學(xué)班十分頭疼的一件事情。不過(guò)，班的 D 對(duì)同學(xué)上小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當(dāng)?shù)淖未_定下來(lái)之后，只有有限會(huì)交頭接耳。在教室中坐成了 M 行N 列，坐在第 i 行第 j 列的同學(xué)的位置是（i，j），為了方便進(jìn)出，在教室中設(shè)置了 K 條橫向的通道，L 條縱向的通道。于是，聰明的小雪想到了一個(gè)辦法，或以減少上學(xué)生交頭接耳：她打算重新擺放桌椅，改變桌椅間通道的

15、位置，因?yàn)槿绻粭l通道隔開(kāi)了兩個(gè)會(huì)交頭接耳的同學(xué)，那么他們就不會(huì)交頭接耳了。請(qǐng)你幫忙給小雪編寫(xiě)一個(gè)程序，給出最好的通道劃分方案。在該方案下，上的學(xué)生對(duì)數(shù)最少。交頭接耳【輸入】輸入文件 seat.in 的第一行，有 5 各用空格隔開(kāi)的整數(shù)，分別是M，N，K，L，D（2=N， M=1000，0=KM，0=LN，D=2000）。接下來(lái) D 行，每行有 4 個(gè)用空格隔開(kāi)的整數(shù)，第i 行的 4 個(gè)整數(shù) Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個(gè)同學(xué)會(huì)交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。輸入數(shù)據(jù)保證最優(yōu)方案的唯一性?！据敵觥枯敵鑫募?seat.out 共兩行。第一行

16、包含 K 個(gè)整數(shù)，a1a2aK，表示第 a1 行和 a1+1 行之間、第 a2 行和第 a2+1 行之間、第 aK 行和第aK+1 行之間要開(kāi)辟通道，其中 ai ai+1，每?jī)蓚€(gè)整數(shù)之間用空格隔開(kāi)（行尾沒(méi)有空格）。第二行包含L 個(gè)整數(shù)，b1b2bk，表示第 b1 列和 b1+1 列之間、第 b2 列和第 b2+1 列之間、第 bL 列和第bL+1 列之間要開(kāi)辟通道，其中 bix2then inc(ax2) else inc(ax1)elseif x1=x2 thenif y1y2then inc(by2) else inc(by1);end;fillchar(ar,sizeof(ar),0); for i:=1 to k dobeginmax:=1;for j:=2 to m do if ajamax then max:=j;amax:=0;inc(ar0);arar0:=max; end;for i:=1 to ar0-1 do for j:=i+1 to ar0 doif ariarj thenbeg:=ari;ari:=arj;arj:=t;end;for i:=1 to ar0-1 do write(ari, );wrin(arar0);fill