在一個(gè)操場的四周擺放著n堆石子?,F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次至少選2堆最多選k堆石子合并成新的一堆,合并的費(fèi)用為新的一堆的石子數(shù)。試設(shè)計(jì)一個(gè)算法,計(jì)算出將n堆石子合并成一堆的最大總費(fèi)用和最小總費(fèi)用。
輸入數(shù)據(jù)的第1行有2個(gè)正整數(shù)n和k,表示有n堆石子,每次至少選2堆最多選k堆石子合并。第2行有n個(gè)數(shù),分別表示每堆石子的個(gè)數(shù)。(貪心算法,要求給出貪心策略)
最優(yōu)解為(1,0,1,0,1),最優(yōu)值為31。
用快速排序算法對序列45,35,65,97,78,13,27進(jìn)行排序。
(每一趟排序以第一個(gè)元素為數(shù)軸。要求每一趟排序有完整的過程。)