本文分享的必刷題目是從藍橋云課、洛谷、AcWing等知名刷題平臺精心挑選而來并結(jié)合各平臺提供的算法標簽和難度等級進行了系統(tǒng)分類。題目涵蓋了從基礎到進階的多種算法和數(shù)據(jù)結(jié)構(gòu)旨在為不同階段的編程學習者提供一條清晰、平穩(wěn)的學習提升路徑。歡迎大家訂閱我的專欄算法題解C與Python實現(xiàn)附上匯總貼算法競賽備考沖刺必刷題C | 匯總【題目來源】洛谷P3650 [USACO1.3] 滑雪課程設計Ski Course Design - 洛谷【題目描述】農(nóng)民約翰的農(nóng)場里有n座山峰每座山都有一個在 0 到 100 之間的整數(shù)的海拔高度。在冬天因為山上有豐富的積雪約翰經(jīng)常開辦滑雪訓練營。不幸的是約翰剛剛得知稅法在滑雪訓練營方面有新變化明年開始實施。在仔細閱讀法律后他發(fā)現(xiàn)如果滑雪訓練營的最高和最低的山峰海拔高度差大于 17 就要收稅。因此如果他改變山峰的高度使最高與最低的山峰海拔高度差不超過 17 約翰可以避免支付稅收。如果改變一座山x單位的高度成本是x^2 單位約翰最少需要付多少錢才能使海拔最高的山峰與海拔最低的山峰的高度只差不超過 17 約翰只愿意改變整數(shù)單位的高度?！据斎搿枯斎氲牡谝恍惺且粋€整數(shù)代表山峰的數(shù)量n。第 2 行到n1行每行一個整數(shù)。第i行的整數(shù)ai代表第i座山的海拔高度?！据敵觥枯敵鲆恍幸粋€整數(shù)代表約翰需要支付修改山海拔高度的總金額?！据斎霕永? 20 4 1 24 21【輸出樣例】18【核心思想】問題分析給定n nn座山峰的海拔高度a i ∈ [ 0 , 100 ] a_i \in [0, 100]ai?∈[0,100]要求將所有山峰高度調(diào)整到某個區(qū)間[ L , L 17 ] [L, L17][L,L17]內(nèi)L LL為整數(shù)使得調(diào)整總成本∑ x i 2 \sum x_i^2∑xi2?最小其中x i x_ixi?為每座山調(diào)整的高度。這是一個枚舉 貪心問題關鍵在于確定最優(yōu)區(qū)間下界L LL。算法選擇排序預處理將山峰高度從小到大排序便于按區(qū)間處理枚舉區(qū)間下界由于原始高度范圍[ 0 , 100 ] [0, 100][0,100]最優(yōu)區(qū)間[ L , L 17 ] [L, L17][L,L17]的L LL只需枚舉[ 0 , 83 ] [0, 83][0,83]因L 17 ≤ 100 L17 \leq 100L17≤100貪心調(diào)整對每個L LL低于L LL的山峰提升到L LL高于L 17 L17L17的山峰降低到L 17 L17L17區(qū)間內(nèi)的山峰不動關鍵步驟讀入數(shù)據(jù)n nn和數(shù)組a [ 1.. n ] a[1..n]a[1..n]排序?qū) aa按升序排列枚舉下界L LLL LL從0 00到83 8383初始化sum 0遍歷每座山a j a_jaj?若a j L a_j Laj?Lsum (L - a_j)^2提升到L LL若a j L 17 a_j L 17aj?L17sum (a_j - L - 17)^2$降低到L 17 L17L17若在[ L , L 17 ] [L, L17][L,L17]內(nèi)不調(diào)整成本為 0更新答案minn min(minn, sum)輸出結(jié)果最小總成本m i n n minnminn時間/空間復雜度時間復雜度O ( 84 ? n ) O ( n ) O(84 \cdot n) O(n)O(84?n)O(n)枚舉 84 個下界每個遍歷n nn座山空間復雜度O ( n ) O(n)O(n)存儲山峰高度數(shù)組枚舉區(qū)間的核心思想?yún)^(qū)間長度固定題目要求極差≤ 17 \leq 17≤17即區(qū)間長度固定為 17只需確定下界L LL最優(yōu)調(diào)整策略對于固定區(qū)間[ L , L 17 ] [L, L17][L,L17]每座山獨立決策——低于下限就提到下限高于上限就降到上限區(qū)間內(nèi)不動。這是因為在區(qū)間約束下每座山的最優(yōu)調(diào)整就是投影到區(qū)間最近端點枚舉范圍壓縮原始高度∈ [ 0 , 100 ] \in [0, 100]∈[0,100]L LL的有效范圍僅為[ 0 , 83 ] [0, 83][0,83]枚舉量極小凸成本特性成本函數(shù)x 2 x^2x2是凸函數(shù)投影到區(qū)間的策略在獨立約束下是最優(yōu)的適用于帶區(qū)間約束的最小化調(diào)整、固定窗口滑動、離散枚舉優(yōu)化等問題【解題思路】【算法標簽】#普及- #貪心【代碼詳解】#includebits/stdc.husingnamespacestd;intn,a[1005],minn1e9;intmain(){cinn;// 輸入nfor(inti1;in;i){// 輸入所有山峰高度cina[i];}sort(a1,an1);// 按照從大到小排序for(inti0;i83;i){// 遍歷山峰的最小高度最高高度就是i17intsum0;// 定義每輪總金額初始為0for(intj1;jn;j){// 遍歷所有山峰if(a[j]i){// 小于最小高度就增加兩者之差需要的成本sum(i-a[j])*(i-a[j]);}elseif(a[j]i17){// 高于最大高度也增加兩者之差需要的成本sum(a[j]-i-17)*(a[j]-i-17);}}minnmin(minn,sum);// 每輪統(tǒng)計后計算最小值}coutminnendl;// 輸出最小值return0;}【運行結(jié)果】5 20 4 1 24 21 18