❶ 貪心演算法總結
做了這10道題，其實發現貪心演算法沒有什麼規律，要說有什麼共同特點就是都是由局部最優從而推出全局最優，每個題基本上都要考慮其局部最優是什麼，其全局最優是什麼，所以雖然都用到了貪心演算法的思想，但是題與題之間又沒有什麼規律可言。
現在把這10道題的思路總結一下（總結主要以我的主觀看法在寫，可能別人看會不知道我在說什麼）
1.分發餅干：
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
思路：想要完成最多的小孩滿足，那麼就得最小的餅干給胃口最小的小孩
這里的貪心思想，
局部最優就是盡可能讓一個餅干喂飽一個
全局最優就是最多的小孩滿足
2.擺動序列：
https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
思路：這里要找到最長的擺動序列，那麼其實就是找那些波峰波谷，如圖所示
可以看出來，在到達波峰波谷的路上有幾個數字不會影響什麼，可以直接去掉。
那麼這里的局部最優就是把單調坡上的點刪掉，保留最多的波峰波谷
全局最優就是得到對多的波峰波谷，即最長的擺動序列
3.最大子序和
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
這道題顯然可以暴力解出來，即列出所有子序和，找出最大的，不過計算量會比貪心大很多。
這里主要介紹貪心解的思想：
想要得到最大子序和，就得保證每次相加時，相加後不能為負數，因為負數繼續往下加一定是拉低總和的，那麼我們當加成到負數時就重新從下個數開始加，並實時記錄最大的子序和，這樣一遍循環就能得出最大子序和。
局部最優：加成負數就立刻停止，並從下個元素重新開始
全局最優：得到最大子序和
4.買賣股票的最佳時機II
https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
思路：想要得到最大利潤，那就要低價買入高價賣出，那麼怎樣的買賣才能得到最大利潤呢。
這里就體現出貪心演算法的「貪」字（我猜的），這道題貪在哪呢，貪在只要有利可圖就去做，即只要今天買入的價錢比明天賣出的價錢底，即有利可圖，那麼我就去做，做就是在今天買入，在明天賣出。
局部最優：得到每天的最大正利潤
全局最優：得到最大利潤
5.跳躍游戲
https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
思路：每個數組的元素代表的是可以跳的最遠下標，那麼我們只要使那個最遠下標包含最後一個下標就是可以跳到，那麼我們每跳到一個位置就要更新那個可以跳的范圍，即可以跳到的最遠下標。
局部最優：每次跳躍都得出最遠的跳躍范圍
全局最優：最後能跳到的最大范圍
6.跳躍游戲II
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
思路：這道題要得到最小的跳躍數，其實只要保證跳的是位置是可以跳范圍內更新最遠范圍的位置就可以了。
為什麼這么說呢？以題例來說：
我們剛開始在『0』的位置，我們能跳到『1』和『2』的位置，那麼我們怎麼跳呢？可以看到跳到『1』之後更新的最大范圍是『4』，跳到『2』之後更新的最大范圍是『3』，所以我們就跳『2』了，因為跳『1』之後更新的最大可跳范圍更大包含了跳『2』的最大可跳范圍，那麼肯定是跳『3』最優呀，這里就體現了局部最優的思想。
局部最優：每次跳後，更新的最大可調范圍最大
全局最優：跳躍次數最少
7.K次取反後最大化的數組和
https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
思路：想要得到最大數組和，我們就可以想到怎樣做呢？
一，盡可能保證負數最少
二，負數絕對值大的優先變正
三，正數絕對值小的優先變負，有零變零
本著這三條原則做，就能做出來。
那麼這道題體現了什麼貪心思想呢？
我感覺，前面那三條都是貪心中『貪』的體現
在負數中，局部最優就是：絕對值大的負數優先變正
在正數中，局部最優就是：絕對值小的正數變負，有零變零
得到的全局最優：數組和最大
8.加油站
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
思路：首先可以想到這道題是可以暴力解出來了，即分別以每個加油站為起點，得出可以跑一圈的加油站
那麼貪心思想做，該怎麼做呢，首先可以想到，如果以一個1點為起點當跑著跑著跑到3，油變為負數時，那麼說明以這個起點是不行的，但是以2或3為起點行不行呢？答案肯定是不行的，因為1跑到3，油變為負，說明1~3的gas=0的，所以可以得出，如果1~3油數變為負數，那麼由2~3油數肯定也為負數。
所以這里就可以得出，如果經過幾個加油站油數變為負了，那麼起點就更新為這一段路的下個加油站跑
局部最優：油量一旦為負，就從下個加油站重新跑
全局最優：得出可以跑一圈的加油站起點
9.分發糖果
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
思路：每個孩子至少一個，如果一個孩子比他旁邊的孩子優秀，就要比他旁邊的糖果多，這道題一旦兩邊都考慮很容易顧此失彼，所以我們就定義兩個循環，分別從左到右，從右到左去考慮，只要更優秀則比他旁邊的多1，如果已經多了就不用變了。
局部最優：保證優秀的孩子比他旁邊的孩子糖果多
全局最優：滿足題中條件，至少要發的糖果
10.檸檬水找零
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
思路：我們在找零時要遵守的規則一定是：
5 得5
10 得10減5
15 得15，優先減一個10減一個5 如果10塊沒有則減三個5
局部最優：以最少用的5塊的方式找零
全局最優：得到找零能否進行下去
❷ 貪心演算法總結 Greedy Algorithms
反證法：亂正
假設貪心不是最優解：
先考慮如何排序
Exchange argument:通過交換元素將最優解轉換為貪心解，但還保持最優性
當cache中不存在所需元素時，需要訪問cache交換元素。
目標：cache misses的次數最少
最優演算法：cache miss時替換當前future queries中最遠訪問的元素。
e.g. future queries中第一個元素g出現cache miss, 需要exchange，判斷current cache中需要替換哪個元素。
在future queries中
思路：構造最優規劃 ，它有最小的cache misses次數；Farthest-In-Future規劃 ,兩者在前 個請求的序列是相同的，如果能證明在第 步時， 可以轉化為 並且沒有增加cache misses的次數，則可以說明 是最優解。
最開始，假設 和 中元素如下：
Case 1: 元素已經在Cache中
假設下一個請求的元素是d顯然兩者都不會發生cache miss，故兩者總的cache misses次數還是相同；
Case 2: 元素不在Cache中， 和 與外界嘩李悔交換相同的元素
假設下一個請求的元素是e,兩者都用a與其交換，有
和 都增加了一次擾扒cache misses，故總cache misses次數還是相同；
Case 3: 元素不在Cache中， 和 與外界交換不同的元素
假設下一個請求的元素是e, 交換a, 交換b,有
之後，下一個請求的元素有四種情況：
Case 3a: 元素在 中, 不在 中; S交換a
也就是請求b,這時S用a交換b,有
有兩次cache misses，而 只有一次，之後 和 序列又保持一致；
Case 3b: 元素在 中, 不在 中; S不交換a
也就是請求b，S用c交換b，有
用a交換c，有
兩者cache misses次數相同，之後 和 序列又保持一致
Case 3c: 元素在 中, 不在 中
即請求a，這種情況不可能發生，因為S_{FF}移出的是最遠需要的元素，即request中a會排在b之後；
Case 3d: 元素不在 和 中
假設請求f, 用a交換f, 用b交換f,有
兩者cache misses次數相同，之後 和 序列又保持一致
的cache misses次數不會多於最優解 , 即 是最優解。
Single-link k-clustering 演算法：
❸ 貪心演算法及其應用
求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。
比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝100KG重量的袋子，怎麼裝才能使得袋子中的豆子價值最大？
我們首先看看這個問題是否符合貪心演算法的使用場景？限制值是袋子100KG，期望值是袋子裡面的價值最高。所以是符合的。那麼我們嘗試著應用下貪心演算法的方法，每一個步驟都尋找當下的最優解，怎麼做呢？
把倉庫裡面的每種豆子價值除以重量，得出每種豆子的單價，那麼當下的最優解，肯定是盡可能最多地裝單價最貴的，也就是先把20KG的黃豆都裝上，然後再把30KG的綠豆都裝上，再裝50KG的紅豆，那麼此時正好裝滿袋子，總價值將是270元，這就是通過貪心演算法求解的答案。
貪心演算法的應用在這個問題上的求解是否是最優解需要一個很復雜的數學論證，我們不用那樣，只要心裡舉幾個例子，驗證下是否比它更好即可，如果舉不出例子，那麼就可以認為這就是最優解了。
雖然貪心演算法雖然在大部分實踐場景中都能得到最優解，但是並不能保證一定是最優解。比如在如下的有向帶權圖中尋找從S到T的最短路徑，那麼答案肯定就是S->A->E->T，總代價為1+4+4=9；
然而，實際上的最短路徑是S->B->D->T，總代價為6。
所以，不能所有這類問題都迷信貪心演算法的求解，但其作為一種演算法指導思想，還是很值得學習的。
除了以上袋子裝豆子的問題之外，還有很多應用場景。這種問題能否使用貪心演算法來解決的關鍵是你能否將問題轉換為貪心演算法適用的問題，即找到問題的限制值和期望值。
我們有m個糖果要分給n個孩子，n大於m，註定有的孩子不能分到糖果。其中，每個糖果的大小都不同，分別為S1,S2,S3...,Sm，每個孩子對糖果的需求也是不同的，為N1,N2,N3...,Nn，那麼我們如何分糖果，才能盡可能滿足最多數量孩子的需求？
這個問題中，限制值是糖果的數量m，期望值滿足最多的孩子需求。對於每個孩子，能用小的糖果滿足其需求，就不要用大的，避免浪費。所以我們可以給所有孩子的需求排個序，從需求最小的孩子開始，用剛好能滿足他的糖果來分給他，以此來分完所有的糖果。
我們有1元、5元、10元、20元、50元、100元紙幣各C1、C5、C10、C20、C50、C100張，現在要購買一個價值K元的東西，請問怎麼才能適用最少的紙幣？
這個問題應該不難，限制值是各個紙幣的張數，期望值是適用最少的紙幣。那麼我們就先用面值最大的100元去付錢，當再加一張100元就超過K時，就更換小面額的，直至正好為K元。
對於n個區間[L1,R1],[L2,R2]...[Ln,Rn]，我們怎麼從中選出盡可能多的區間，使它們不相交？
我們需要把這個問題轉換為符合貪心演算法特點的問題，假設這么多區間的最左端點是Lmin，最右端點是Rmax，那麼問題就是在[Lmin,Rmax]中，選擇盡可能多的區間往裡面塞，並且保證它們不相交。這里，限制值就是區間[Lmin,Rmax]，期望值就是盡可能多的區間。
我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。
貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。
❹ (三) 貪心演算法
貪心演算法的思想非常簡單且演算法效率很高，在一些問題的解決上有著明顯的優勢。
假設有3種硬幣，面值分別為1元、5角、1角。這3種硬幣各自的數量不限，現在要找給顧客3元6角錢，請問怎樣找才能使得找給顧客的硬幣數量最少呢？
你也許會不假思索的說出答案：找給顧客3枚1元硬幣，1枚5角硬幣，1枚1角硬幣。其實也可以找給顧客7枚5角硬幣，1枚1角硬幣。可是在這里不符合題意。在這里，我們下意識地應用了所謂貪心演算法解決這個問題。
所謂貪心演算法，就是 總是做出在當前看來是最好的選擇(未從整體考慮) 的一種方法。以上述的題目為例，為了找給顧客的硬幣數量最少，在選擇硬幣的面值時，當然是盡可能地選擇面值大的硬幣。因此，下意識地遵循了以下方案：
（1）首先找出一個面值不超過3元6角的最大硬幣，即1元硬幣。
（2）然後從3元6角中減去1元，得到2元6角，再找出一個面值不超過2元6角的最大硬幣，即1元硬幣。
（3）然後從2元6角中減去1元，得到1元6角，再找出一個面值不超過1元6角的最大硬幣，即1元硬幣。
（4）然後從1元6角中減去1元，得到6角，再找出一個面值不超過6角的最大硬幣，即5角硬幣。
（5）然後從6角中減去5角，得到1角，再找出一個面值不超過1角的最大硬幣，即1角硬幣。
（6）找零錢的過程結束。
這個過程就是一個典型的貪心演算法思想。
貪心策略總是做出在當前看來是最優的選擇，也就是說貪心策略並不是從整體上加以考慮，它所做出的選擇只是在某種意義上的 局部最優解 ，而許多問題自身的特性決定了該問題運用貪心策略可以得到最優解或較優解。(註：貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。）
貪心演算法沒有固定的演算法框架，演算法設計的關鍵是 貪心策略的選擇 。選擇的貪心策略必須具備無後效性。
貪心策略 適用的前提 是：
嚴格意義上講，要使用貪心演算法求解問題，該問題應當具備以下性質：
注意 ：對於一個給定的問題，往往可能有好幾種量度標准。初看起來，這些量度標准似乎都是可取的，但實際上，用其中的大多數量度標准作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。
因此， 選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心 。
實際上，貪心演算法 適用的情況很少 。一般，對一個問題分析是否適用於貪心演算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。
最優解問題大部分都可以拆分成一個個的子問題(多階段決策問題)，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。
貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。
動態規劃方法代表了這一類問題的一般解法， 自底向上 構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。
而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始( 自頂向下 )，選擇最優的路，一直走到底就可以了。
一個問題分為多個階段，每個階段可以有n種決策，各個階段的決策構成一個決策序列，稱為一個策略。
這兩種演算法都是選擇性演算法，在進行決策的選擇時：
前提是這個問題得具有貪心選擇性質，需要證明(數學歸納法(第一、第二))，如果不滿足那就只能使用動態規劃解決。(一旦證明貪心選擇性質，用貪心演算法解決問題比動態規劃具有更低的時間復雜度和空間復雜度。)
從范疇上來看：
Greedy ⊂ DP ⊂ Searching （貪心是動規的特例）
即所有的貪心演算法問題都能用DP求解，更可以歸結為一個搜索問題，反之不成立。
貪心演算法所作的選擇可以依賴於以往所作過的選擇，但決不依賴於將來的選擇，也不依賴於子問題的解，這使得演算法在編碼和執行的過程中都有著一定的速度優勢。如果一個問題可以同時用幾種方法解決，貪心演算法應該是最好的選擇之一。但是貪心演算法並不是對所有的問題都能得到整體最優解或最理想的近似解，與回溯法等比較，它的適用區域相對狹窄許多，因此正確地判斷它的應用時機十分重要。
一步一步地進行，常 以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況 ，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。
它採用 自頂向下 ，以 迭代 的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以 貪心法不需要回溯 。
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。
❺ 5. 設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti，1<=i<=n。應如何安排n個顧客的服務次序才能
上面的 思路不錯
最優服務次序問題
一、問題描述：
設有n 個顧客同時等待一項服務。顧客i需要的服務時間為ti, 1≦i ≦n 。共有s處可以提供此服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n 個顧客等待服務時間的總和除以n。
二、貪心選擇策略
假設原問題為T，而我們已經知道了某個最優服務系列，即最優解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為：
T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；
那麼總等待時問，即最優值為：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)；
由於平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。
本問題採用貪心演算法求解，貪心策略如下：對服務時間最短的顧客先服務的貪心選擇策略。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇後，原問題T變成了需對n-1個顧客服務的新問題T』。新問題和原問題相同，只是問題規模由n減小為n-1。基於此種選擇策略，對新問題T』，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為止 。
三、問題的貪心選擇性質
先來證明該問題具有貪心選擇性質，即最優服務A中t(1)滿足條件：t(1)<=t(i)(2<i<n)。
用反證法來證明：假設t(1)不是最小的，不妨設t(1)>t(i)(i>1)。
設另一服務序列B=（t(i)，t(2)，…，t(1)…，t(n)）
那麼TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0
即TA>TB，這與A是最優服務相矛盾。
故最優服務次序問題滿足貪心選擇性質。
四、問題的最優子結構性質
在進行了貪心選擇後，原問題T就變成了如何安排剩餘的n-1個顧客的服務次序的問題T』，是原問題的子問題。
若A是原問題T的最優解，則A』={t(2)，…t(i)…t(n))是服務次序問題子問題T』的最優解。
證明：假設A』不是子問題T』的最優解，其子問題的最優解為B』，則有TB』<TA』，而根據TA的定義知，TA』十t(1)=TA。因此TB』+t(1)<TA』+t(1)=TA，即存在一個比最優值TA更短的總等待時間，而這與TA為問題T的最優值相矛盾。因此，A』是子問題T』的最優值。
從以上貪心選擇及最優子結構性質的證明，可知對最優服務次序問題用貪心演算法可求得最優解。
根據以上證明，最優服務次序問題可以用最短服務時間優先的貪心選擇可以達到最優解。故只需對所有服務先按服務時間從小到大進行排序，然後按照排序結果依次進行服務即可。平均等待時間即為TA/n。
五、演算法實現
由多處最優服務次序問題具有貪心選擇性質和最優子結構性質，容易證明演算法greedy的正確性。本演算法採用最短服務時間優先的貪心策略。首先將每個顧客所需要的服務時間從小到大排序。然後申請2個數組：st[]是服務數組，st[j]為第j個隊列上的某一個顧客的等待時間；su[]是求和數組，su[j]的值為第j個隊列上所有顧客的等待時間；
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;//循環分配顧客到每一個服務點上
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
六、演算法測試結果
七、演算法復雜性分析
程序主要是花費在對各顧客所需服務時間的排序和貪心演算法，即計算平均服務時間上面。其中，貪心演算法部分只有一重循環影響時間復雜度，其時間復雜度為O(n)：而排序演算法的時間復雜度為O(nlogn)。因此，綜合來看演算法的時間復雜度為O(nlogn)。
八、參考文獻
[1] 王曉東.計算機演算法設計與分析(第3版)[M]．北京：電子工業出版社,2007．
[2] 陳媛.《演算法與數據結構》[M],清華大學出版社, 第1版,2005.4.
[3] 王曉東.演算法設計與實驗題解 [M]．北京：電子工業出版社,2008．
附錄（程序代碼）
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
void main()
{int n;//等待服務的顧客人數
int s;//服務點的個數
int i;
int a;
int t;//平均服務時間
vector<int>x;
cout<<"please input the num of the customer:"<<endl;
cin>>n;
cout<<"please input the num of the server:"<<endl;
cin>>s;
cout<<"please input the need service time of each customer:"<<endl;
for(i=1;i<=n;i++){
cout<<"No."<<i<<endl;
cin>>a;
x.push_back(a);
}
t=greedy(x, s);
cout<<"the least average waiting time is:"<<t<<endl;
}