本篇博客側(cè)重于貪心法正確性證明
原問題可以二分答案轉(zhuǎn)變?yōu)橐粋€判定問題，
該判定問題如下：
有n個集合A1,A2,...,An，它們的元素個數(shù)分別是r1,r2,...,rn，且相鄰兩集合不交（包括首尾即A1與An），現(xiàn)給定一常數(shù)k使得這n個集合一共至多有k個不同元素，顯然k太小時這樣的n個集合是不可能存在的，請你在O(n)時間內(nèi)判定某個給定的k是否合法。
首先給出算法：
不妨設(shè)這n個集合的元素取自{1,2,3,...,k}
對于n為偶數(shù)的情況，
取A1={1,2,...,r1}，即前r1個數(shù)，取A2為{k,k-1,k-2,...,k-(r2-1)}，即后r2個數(shù)，A3為前r3個數(shù)...依次類推，如果過程中沒有發(fā)生元素不夠用的情況，則k合法。
對于n為奇數(shù)的情況，
取A1={1,2,...,r1}，即前r1個數(shù)，取A2為{r1+1,r1+2,...,r1+r2}，即r1之后緊鄰的r2個數(shù)，然后A3盡量取靠后(大)的元素，A4盡量取靠前(小)的元素...依此類推，如果過程中沒有發(fā)生元素不夠用的情況，則k合法。
這樣做為什么是對的呢？
下圖是n為偶數(shù)時的情況，從上到下分別是A1、A2、A3、A4...，整個矩形表示1~k共k個元素，陰影部分表示這個集合選定了哪些元素，A1選前r1個，A2選后r2個，A3選前r3個...
不難發(fā)現(xiàn)，對于n為偶數(shù)的情況算法的正確性是顯然的。
n為奇數(shù)的情況比較棘手，我們先把構(gòu)造過程用圖形直觀地呈現(xiàn)出來，如下圖。
這時A1選前r1個，A2選不與A1沖突的盡量小的r2個元素，A3選不與A2沖突的盡量大的r3個元素...
然后我們發(fā)現(xiàn)這個過程中有一些特點，比如每個集合的元素至多是連續(xù)的兩段，比如有一個位置在每一個集合中都會出現(xiàn)（圖中灰色豎線）。
上圖把每個集合超出灰線的部分標(biāo)記為紅色，因為最終An要和A1判斷是否沖突，所以我們的目標(biāo)是讓An的紅色部分為0，等價于讓An的紅色部分最少。然后我們注意到這樣一個遞推性質(zhì)：Ak的紅色部分最少的充要條件是Ak-1的紅色部分最少。
由此，我們說明了n為奇數(shù)時算法的正確性。
