2、k之后的人無影響，對sk之前的人等待都減少了，(s1-sk)>0,從而新的序列比原最優(yōu)序列好，這與假設(shè)矛盾，故s1為最小時間，同理可證s2…sn依次最小。例3．:數(shù)列極差問題【題目描述】在黑板上寫了N個正整數(shù)做成的一個數(shù)列，進(jìn)行如下操作：每一次擦去其中的兩個數(shù)a和b，然后在數(shù)列中加入一個數(shù)a×b+1，如此下去直至黑板上剩下一個數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的max，最小的為min，則該數(shù)列的極差定義為M=max-min。編程任務(wù)：對于給定的數(shù)列，編程計(jì)算出極差M。輸入輸出樣例：輸入：42143輸出：13【算法分析】當(dāng)看到此題時，我們會發(fā)現(xiàn)求max與求min是兩
3、個相似的過程。若我們把求解max與min的過程分開，著重探討求max的問題。下面我們以求max為例來討論此題用貪心策略求解的合理性。討論：假設(shè)經(jīng)（Ｎ－3）次變換后得到３個數(shù)：a,b,max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）個數(shù)經(jīng)（Ｎ－３）次ｆ變換后所得的最大值，此時有兩種求值方式，設(shè)其所求值分別為z1，z2，則有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若經(jīng)（Ｎ－２）次變換后所得的３個數(shù)為：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不為（Ｎ－２）次變換后的最大值，即ｍ＜max＇則此時所求得的最大值為：z3＝（ａ×
4、ｂ+１）×ｍ+１此時z1－z3＝(１+ａｂ）（max＇－ｍ）＞０ 所以此時不為最優(yōu)解。所以若使第ｋ（１≤ｋ≤Ｎ－１）次變換后所得值最大，必使（ｋ－１）次變換后所得值最大（符合貪心策略的特點(diǎn)2），在進(jìn)行第ｋ次變換時，只需取在進(jìn)行（ｋ－１）次變換后所得數(shù)列中的兩最小數(shù)ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合貪心策略特點(diǎn)1），因此此題可用貪心策略求解。在求ｍin時，我們只需在每次變換的數(shù)列中找到兩個最大數(shù)ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。這是一道兩次運(yùn)用貪心策略解決的一道問題，它要求選手有較高的數(shù)學(xué)推理能力。例4．整數(shù)區(qū)間range.cpp【題目
5、描述】我們定義一個整數(shù)區(qū)間[a,b],a,b是一個從a開始至b結(jié)束的連續(xù)整數(shù)的集合。編一個程序，對給定的n個區(qū)間，找出滿足下述條件的所含元素個數(shù)最少的集合中元素的個數(shù)：對于所給定的每一個區(qū)間，都至少有兩個不同的整數(shù)屬于該集合。(1<=n<=10000,0<=a<=b<=1000)輸入輸出格式：輸入：第一行一個正整數(shù)n，接下來有n行，每行給定一個區(qū)間的a,b值輸出：一個正整數(shù)，即滿足條件的集合所包含的最少元素個數(shù)輸入輸出樣例輸入：輸出：4436240247【算法分析】本題數(shù)據(jù)規(guī)模較大，用搜索做會超時，而動態(tài)規(guī)劃無從下手。考慮貪心算法。題目意思是要找一個集合，該集合中的數(shù)的個數(shù)
6、既要少又要和所給定的所有區(qū)間有交集。（每個區(qū)間至少有兩個該集合中的數(shù)）。我們可以從所給的區(qū)間中選數(shù)，為了選盡量少的數(shù)，應(yīng)該使所選的數(shù)和更多的區(qū)間有交集這就是貪心的標(biāo)準(zhǔn)。一開始將所有區(qū)間按照右端點(diǎn)從小到大排序。從第一個區(qū)間開始逐個向后檢查，看所選出的數(shù)與所查看的區(qū)間有無交集，有兩個則跳過，只有一個數(shù)相交，就從當(dāng)前區(qū)間中選出最大的一個數(shù)（即右端點(diǎn)），若無交集，則從當(dāng)前區(qū)間選出兩個數(shù)，就（右端點(diǎn)，右端點(diǎn)-1），直至最后一個區(qū)間。#include//整數(shù)區(qū)間問題usingnamespacestd;structprince{intleft,right;//區(qū)間左右
7、端點(diǎn)}a[10000];intn;intresult;//存放結(jié)果中的數(shù)intcmp(constvoid*a,constvoid*b){return(*(prince*)a).right-(*(prince*)b).right;}intwork(){qsort(a+1,n,sizeof(a[0]),cmp);//按區(qū)間右端點(diǎn)由小到大排序inti,j,k;inta1,a2;a1=a[1].right-1;a2=a[1].right;result=2;for(i=2;i<=n;i++){if(a[i].left<=a1
