第三次課貪心算法

1、第三次課貪心算法第1頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六第3章 內(nèi)容提綱3.1 貪心算法的基本思想3.2 刪數(shù)問題3.3 裝箱問題第2頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六 顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。第3頁(yè)，共73

2、頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六活動(dòng)安排問題 活動(dòng)安排問題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。第4頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六活動(dòng)安排問題 設(shè)有n個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si fi 。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間

3、si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與活動(dòng)j相容。第5頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六活動(dòng)安排問題templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 下面給出解活動(dòng)安排問題的貪心算法GreedySelector :各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間

4、的非減序排列 第6頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六活動(dòng)安排問題 由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。 第7頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六 算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的

5、活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。 第8頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六活動(dòng)安排問題 例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011Si130535688212fi4567891011121314第9頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六活動(dòng)安排問題 算法greedySelector 的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。第10頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45

6、分，星期六活動(dòng)安排問題 若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。第11頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解

7、的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 第12頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素1、貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體

8、最優(yōu)解。第13頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素 當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 2、最優(yōu)子結(jié)構(gòu)性質(zhì)第14頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動(dòng)態(tài)規(guī)劃算法的主

9、要差別。3、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異第15頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素0-1背包問題： 給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。第16頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1

10、in。 這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 第17頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁(yè)： 用貪心算法解背包問題的基本步驟：第18頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素

11、void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i=n;i+) xi=0; float c=M; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; 算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。第19頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六貪心算法的基本要素 對(duì)于0-1背包問題

12、，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。 第20頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六3.2 刪數(shù)問題給定一個(gè)高精度的正整數(shù)N（不超過240位），去掉任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序組成一個(gè)新的正整數(shù)。編程對(duì)于給定的N和S，尋找一種方案使得剩下的數(shù)字

13、組成的新數(shù)最小示例：N=178543， S=4則結(jié)果為：13第21頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六算法分析N的存儲(chǔ)只能采用數(shù)組，可選擇字符數(shù)組；可采用貪心算法，即：共刪掉S個(gè)數(shù)，每一步刪掉一個(gè)數(shù)，并且總選擇一個(gè)使剩下的數(shù)最小的數(shù)符刪去。為了保證刪1個(gè)數(shù)符后的數(shù)最小，可以按照從高位到低位的方向收縮遞減區(qū)間，如果不存在遞減區(qū)間則刪尾數(shù)符；否則刪掉遞減區(qū)間的首字符，這樣形成一個(gè)新的數(shù)串。然后回到串首，重復(fù)上面的規(guī)則，刪下一個(gè)數(shù)符，。，直至刪除S個(gè)數(shù)符為止。第22頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六17854317543154314313第23頁(yè)，共73

14、頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六17853417534153413413第24頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六 程序#include #include using namespace std;int s;class nodepublic:char c;node *next;class queepublic:node *first;第25頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六quee *init()char str250; quee *n; node *tmp; node * tail;n=new quee; n-first=NULL

15、; cinstr; cins;int i=0;while(stri!=0)tmp=new node;tmp-c=stri; tmp-next=NULL;if(n-first=NULL)n-first=tmp; tail=tmp;elsetail-next=tmp; tail=tmp;i+;return n;第26頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六void del(quee *start, node *p)node *x;x=start-first;if (x-next)while(x-next!=p) x=x-next;x-next=p-next;delete p;第2

16、7頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六void print(quee *start)node *tmp;if(start-first=NULL) return;tmp=start-first;while(tmp)printf( %c,tmp-c);tmp=tmp-next;printf(n);第28頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六node *find(quee *start)node *tmp;tmp=start-first;while(tmp-next!=NULL & tmp-cnext-c)tmp=tmp-next;return tmp;第2

17、9頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六int main(int argc, char* argv)quee *n;node *p;n=init();while(s!=0)p=find(n);del(n,p);s-;print(n);return 0;第30頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六3.3 POJ 1017Packets第31頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets題意已知：有6*6 的大箱子和 1*1，2*2，3*3，4*4，5*5，6*6 的木塊(平面)問：給定各種木塊的數(shù)目，求最少需要多少個(gè)大箱子來裝？例

18、如：輸入：0 0 4 0 0 1 - 輸出 2輸入：7 5 1 0 0 0 - 輸出 1第32頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets解題思想： 貪心準(zhǔn)則：先放大的，后放小的6*6的木塊每個(gè)占用一個(gè)箱子；5*5的木塊每個(gè)占用一個(gè)新箱子，余下11個(gè)1*1的空格；4*4的木塊每個(gè)占用一個(gè)新箱子，余下5個(gè)2*2的空格。4. 3*3的木塊每4個(gè)占用新一個(gè)箱子，不足4個(gè)也占一個(gè)新箱子，分情況余下不同數(shù)目的空格；5. 2*2的木塊先填空格，空格不足開新箱子，每9個(gè)2*2的木塊占一個(gè)新箱子；6. 1*1的木塊先填空格，空格不足開新箱子，每36個(gè)占一個(gè)新箱子。第33頁(yè)，共73頁(yè)

19、，2022年，5月20日，22點(diǎn)45分，星期六Packets假設(shè) 6*6，5*5，4*4 ，3*3，2*2，1*1的箱子個(gè)數(shù) b6 b5 b4 b3 b2 b1第34頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets 4*4，5*5，6*6的塊單獨(dú)開新的箱子。每一個(gè)5*5的塊還能放下11個(gè)1*1的箱子。每一個(gè)4*4的塊還能放下5個(gè)2*2的箱子，或者放下20個(gè)1*1的箱子。4*4塊5*5塊6*6塊第35頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六 3*3的塊1-4塊占一個(gè)新箱子，一個(gè)箱子可放下4個(gè)3*3的塊。如果一個(gè)箱子放下了1個(gè)3*3的塊，則還可放下5個(gè)2*

20、2的塊和7個(gè)1*1的塊?；蛘呖梢苑畔?7個(gè)1*1的塊。如果一個(gè)箱子放下了2個(gè)3*3的塊，則還可放下3個(gè)2*2的塊和6個(gè)1*1的塊?；蛘呖梢苑畔?8個(gè)1*1的塊。如果一個(gè)箱子放下了3個(gè)3*3的塊，則還可放下1個(gè)2*2的塊和5個(gè)1*1的塊?；蛘呖梢苑畔?個(gè)1*1的塊。第36頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六PacketsnTotal - 箱子數(shù)1） 先放好所有 6 * 6, 5 * 5, 4 * 4 和3 * 3 的木塊nTotal = b6 + b5 + b4 + (b3+3)/4 4*4, 5*5, 6*6 單獨(dú)開新的箱子 3*3 每 1-4 個(gè)占一個(gè)新箱子 2）再把2

21、 * 2的塞到放有3*3木塊的箱子里 int Contain24 = 0, 5, 3, 1 ; Contain2i 表示當(dāng)箱子里有i個(gè) 3*3的木塊時(shí)，還能放下多少個(gè)2*2的木塊3） 考慮放有3*3的木塊的箱子在塞滿2*2的木后還能放多少個(gè)1*1的木塊：int Contain14 = 0, 7, 6, 5 ; Contain1i 表示當(dāng)箱子里有i個(gè) 3*3的木塊，并且還填滿了2*2的木塊后，還能放下多少個(gè)1*1的木塊。第37頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets 如果箱子里放1個(gè)3*3木塊，那么還能放5個(gè)2*2木塊,以及7個(gè)1*1木塊第38頁(yè)，共73頁(yè)，202

22、2年，5月20日，22點(diǎn)45分，星期六Packets 如果箱子里放2個(gè)3*3木塊，那么還能放3個(gè)2*2木塊,以及6個(gè)1*1木塊第39頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets 如果箱子里放3個(gè)3*3木塊，那么還能放1個(gè)2*2木塊,以及5個(gè)1*1木塊第40頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets4) 計(jì)算放好6*6,5*5,4*4,3*3后留下多少空格能放2*2c2 = b4 * 5 + Contain2b3 % 4;留下多少空格能放1*1 c1 = b5 * 11 + Contain1b3 % 4 (能放2*2的地方暫不考慮放1*1

23、，因?yàn)槿绻鹀2b2則多余的b2-c2個(gè)位置可以放4*(b2-c2)個(gè)1*1的箱子)第41頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六Packets5) 放 2 * 2，如果不夠放，就開新箱子，放完2*2，計(jì)算還剩多少空格能放1*1。if ( b2 c1 ) nTotal += ( b1 - c1 ) / 36;if( b1 - c1) % 36 )nTotal +;cout nTotal endl;Packets第43頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六#include int Contain14 = 0, 7, 6, 5 ; int Contain24 =

24、 0, 5, 3, 1 ; int nTotal;void main() int b1,b2,b3,b4,b5,b6; for(;) cinb1b2b3b4b5b6; if(b1=0 & b2=0 & b3=0 & b4=0 & b5=0 & b6=0) break;nTotal = b6 + b5 + b4 + b3/ 4; if( b3 % 4) nTotal +;int c1; /當(dāng)前能放 1*1 木塊的空格數(shù)目c1 = b5 * 11; /每個(gè)放5*5的箱子，還能放11個(gè) 1 * 1 的木塊c1 += Contain1b3 % 4 ; /加上3*3箱子里能放的數(shù)目int c2; /當(dāng)前

25、能放 2*2 木塊的空格數(shù)目（先不考慮將1*1的木塊放在 / 2*2的空格里）c2 = b4 * 5; /每個(gè)放5*4的箱子，還能放5個(gè) 2 * 2 的木塊c2 += Contain2b3 % 4; /加上3*3箱子里能放的數(shù)目第44頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六if ( b2 c1 ) nTotal += ( b1 - c1 ) / 36;if( b1 - c1) % 36 )nTotal +;cout nTotal endl; 第45頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六案例3水位 為使房屋買主可以評(píng)估洪水保險(xiǎn)的開銷，一家真實(shí)的房地產(chǎn)公司提供

26、了一種客戶端程序，此程序現(xiàn)實(shí)了可能被購(gòu)買得房屋所在地區(qū)以100平方米為單位的海拔高度。雨水、雪水和管道破裂流出的水將會(huì)匯聚到海拔最低，因?yàn)樗畷?huì)從高處流向低處。為簡(jiǎn)化問題，我們假設(shè)水沿著排水溝從高出流向低處，并且水不會(huì)被土地所吸收。第46頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六從天氣信息的檔案中，我們得知了一個(gè)區(qū)域的典型儲(chǔ)水量。作為預(yù)期的購(gòu)房者，我們希望知道低處積水后的水位，以及完全被淹沒在水中的面積占此地區(qū)的百分比(也就是，10平方米的海拔高度嚴(yán)格低于水平面)。你被要求寫一個(gè)程序來給出結(jié)果。 第47頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六輸入數(shù)據(jù)輸入包括區(qū)域

27、描述所構(gòu)成的一個(gè)序列。每個(gè)由一對(duì)整數(shù)m和n開始，每個(gè)都小于30，給定的區(qū)域都是100平方米。緊隨其后的是m行，每行n個(gè)整數(shù)，給出地區(qū)海平面，以主行序給出。高度的單位是米，分別用正數(shù)或者負(fù)數(shù)表明高于或低于海平面。每個(gè)區(qū)域最后一個(gè)值是一個(gè)整數(shù)，用以指出有多少立方米的水聚集到此區(qū)域。m和n為兩個(gè)0代表輸入結(jié)束。第48頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六輸出描述對(duì)每個(gè)區(qū)域，顯示區(qū)域編號(hào)(1,2,)，水平面(以米為單位表示高于或低于海平面)以及此區(qū)域被水淹沒的面積，每個(gè)占一行。水位和被水淹沒面積的百分率顯示時(shí)保留2位小數(shù)每個(gè)區(qū)域輸出后跟一個(gè)空行。第49頁(yè)，共73頁(yè)，2022年，5月

28、20日，22點(diǎn)45分，星期六樣例3 325 37 4551 12 3494 83 27100000 0 Region 1Water level is 46.67 meters.66.67 percent of the region is under water.第50頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六解題思路由于題目中特別聲明水無論如何都會(huì)流到當(dāng)前水面最低的地方，使得問題一下子簡(jiǎn)化了。很容易想到以下貪心算法：（1）把每個(gè)格子的高度排序；（2）以低格子到高格子的順序填水，把水均勻的鋪在當(dāng)前的水面上，并不斷更新當(dāng)前水面面積，和剩余水量；（3）若剩余水量為0，輸出當(dāng)前水面高度

29、和水面覆蓋率。第51頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六注意1水面每達(dá)到一個(gè)格子的高度，水面的面積也要隨之?dāng)U大；2高度有負(fù)值，水面的初始高度是最低格子的高度而不是0；3考慮好若干個(gè)格子高度相等的情況；4每個(gè)格子的面積是100；5沒有水時(shí)，覆蓋率為0；6水若剛好達(dá)到一個(gè)格子的高度，此格子不算被水覆蓋；7水面達(dá)到最高格子后，要把剩下的水均勻的鋪在整個(gè)區(qū)域上；8注意浮點(diǎn)數(shù)的計(jì)算誤差，因?yàn)檫@個(gè)原因大家在POJ上都沒有通過此題:- 第52頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六#include #include int h1000000; / 保存每個(gè)格子的高度值

30、，因不知m和n的范圍，故設(shè)的比較大int cmp(const void *a, const void *b) return *(int *)a) - *(int *)b);第53頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六main() int t, m, n, nn; double x, hw; int i; t = 0;第54頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六 while(1) /輸入 scanf(%d%d, &n, &m); if(n = 0 & m = 0) break; t+; nn = m * n; for(i = 0; i 0) for(i =

31、 1; i nn; i+) /在高度相等的情況下，擴(kuò)大水面面積 while(i nn & hi = hi - 1) i+; if(i = nn | x 0) / 若剩下水，就把它鋪在當(dāng)前的范圍上 while(i 1且B/A=BA，則C=B/A若A1，則C=B,打印1/C轉(zhuǎn)步驟（2）。第61頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六#include #include int num;int a,b;int c;int zc(int a,int b) int xx; xx=b/a; if(xx*a=b) return 1; return 0;第62頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六void calab() while(1) c=(b/a)+1; a=a*c-b; b=b*c; printf(%d,c); if(a1 & zc(a,b) printf(%dn,b/a); break; else if(a=1) printf(%dn,b); break; ;第63頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六main() int i; scanf(%dn,&num); for(i=1;i=num;i+) scanf(%d %dn,&a,&b); calab(); 第64頁(yè)，共73頁(yè)，2022年，5月20日，22點(diǎn)45分，星期六