貪心演算法是從問題的某一個初始狀態出發，通過逐步構造最優解的方法向給定目標前進，并期望通過這種方法產生出一個全域最優解的方法，
貪心演算法的特點是貪心標準選擇與最優子結構，
貪心標準選擇：應用當前最好的標準作為統一標準，將原問題變為一個相似的但規模更小的子問題，之后的每一步選出來的一定是原問題最優解的一部分，如果一個問題貪心后只剩下一個子問題且有最優子結構時可以使用貪心演算法，
最優子結構：當一個問題的最優解包含子問題的最優解時則此問題具有最優子結構性質，
解題步驟：1.設計資料找規律；2.進行貪心猜想；3.正確性證明（列舉反例的一般證明和數學歸納與反證法的嚴格證明）；4.程式實作，
第一題 NOIP2012 國王游戲
恰逢 HH國國慶，國王邀請nn 位大臣來玩一個有獎游戲，首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數，然后，讓這 nn 位大臣排成一排，國王站在隊伍的最前面，排好隊后，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果，國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少，注意，國王的位置始終在隊伍的最前面，
輸入格式
第一行包含一個整數nn，表示大臣的人數，
第二行包含兩個整數 aa和 bb，之間用一個空格隔開，分別表示國王左手和右手上的整數，
接下來 nn行，每行包含兩個整數aa 和 bb，之間用一個空格隔開，分別表示每個大臣左手和右手上的整數，
輸出格式
一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數，
輸入輸出樣例
輸入 3 1 1 2 3 7 4 4 6 輸出 2解題分析：相鄰兩個人交換對前面的人答案沒影響，對后面的人答案也沒影響，即相鄰兩人位置的交換只會對這個人產生影響，因此可以從這里為切入點，討論二元組順序對結果的影響，
可以設定這兩個人的位置分別為i，i+1.左手數字為a[i]、a[i+1]，右手數字為b[i]、b[i+1],兩人的金幣數為w[i]、w[i+1]，
設P[i]=a[1]*a[2]*a[3]*...*a[i]
未調換順序時，k1=w[i]=P[i-1]/b[i],k2=w[i+1]=P[i]/b[i+1].ans1=max(k1,k2).
調換順序后，k3=P[i-1]/b[i+1],k4=P[i-1]*a[i+1]/b[i],ans2=max(k3,k4).
顯然有k1<k4,k3<k2.如果ans1<ans2那么必有k2<k4.化簡可以得到a[i]*b[i]<a[i+1]*b[i+1],這表明如果把a[i],b[i]放在后面則會導致得到的結果相比調換前會增加，所以為了使ans取到最小值應該把a[i]*b[i]較小的放在前面，以a[i]*b[i]為關鍵字排序，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253424.html
標籤：其他
上一篇：照片里的秘密，你看到的不是你認為的，這種造假方法能同時騙過AI和人眼
下一篇：高精度演算法