目錄
貪心思想
一、Dijkstra最短路問題
問題描述：
貪心策略：
二、Prim 和 Kruskal 最小生成樹問題
Prim 算法：
Kruskal 算法：
三、Huffman樹問題
問題描述：
貪心策略：
四、背包問題
問題描述：
貪心策略：
五、硬幣找零問題
問題描述：
貪心策略：
六、區間合并問題
問題描述：
貪心策略：
七、選擇不相交區間問題
問題描述：
貪心策略：
八、區間選點問題
問題描述
貪心策略
九、區間覆蓋問題
問題描述：
貪心策略：
十、區間分組問題
問題描述：
貪心策略：
十一、任務調度問題
問題描述：
貪心策略：
十二、加油站問題
問題描述：
貪心策略：
十三、跳躍游戲
問題描述：
貪心策略：
十四、跳躍游戲 II
問題描述：
貪心策略：
?十五、股票買賣問題
問題描述：
貪心策略：
十六、最小代價貪心問題
問題描述：
貪心策略：
1.https://codeforces.com/contest/2118/problem/C
思路：
代碼：
2.https://codeforces.com/contest/1722/problem/D
思路：
代碼：
十七、其他
1.B-黃_牛客小白月賽118
思路：
代碼：
2.https://codeforces.com/problemset/problem/2116/B
思路及代碼：cf2116B-CSDN博客
3.https://codeforces.com/problemset/problem/2067/B
思路及代碼：cf2067B-CSDN博客
4.https://codeforces.com/problemset/problem/2059/B
思路及代碼：cf2059B-CSDN博客
5.https://codeforces.com/contest/1760/problem/E
思路：
代碼：
6.https://codeforces.com/contest/2110/problem/C
?思路及代碼：cf2110C-CSDN博客
貪心思想
????????貪心算法（Greedy Algorithm）是一種在求解問題時，每一步都選擇當前最優解，以期望最終得到全局最優解的算法思想。貪心算法的基本思想可以總結為“每一步都做出一個局部最優的選擇，最終就能得到全局最優解”。
一、Dijkstra最短路問題
問題描述：
在一個圖中，找到從起點到其他所有點的最短路徑（適用于無負邊權的情況）。
貪心策略：
每次擴展離源點最近的未訪問節點。
二、Prim 和 Kruskal 最小生成樹問題
Prim 算法：
從任意一個頂點開始，逐步加入與當前樹連接權重最小的邊。
Kruskal 算法：
按邊權從小到大排序，依次加入不會形成環的邊。
三、Huffman樹問題
問題描述：
構造一個帶權路徑長度最小的二叉樹，用于數據壓縮中的最優前綴編碼。
貪心策略：
每次合并兩個頻率最小的節點。
四、背包問題
問題描述：
物品可以取部分，目標是在容量限制下最大化總價值。
貪心策略：
按單位重量價值從高到低依次選取。
五、硬幣找零問題
問題描述：
給定不同面值的硬幣，求最少數量湊出某個金額。
貪心策略：
優先使用最大面值的硬幣。
六、區間合并問題
問題描述：
給定多個區間，合并所有有重疊或相鄰的區間，返回合并后的無重疊區間列表。
貪心策略：
按左端點排序后依次處理，若當前區間與結果中最后一個區間重疊，則合并。
七、選擇不相交區間問題
問題描述：
給定多個時間區間，從中選擇盡可能多的互不重疊的區間。
貪心策略：
按右端點從小到大排序，每次選擇最早結束的區間，跳過與其沖突的區間。
八、區間選點問題
問題描述
在每個區間中至少選一個點，使得這些點覆蓋所有區間，要求所選點的數量最少。
貪心策略
按右端點排序，每次在當前未被覆蓋的區間的右端點上選一個點。
九、區間覆蓋問題
問題描述：
給定一個目標區間和若干子區間，判斷是否能用這些子區間完全覆蓋目標區間。
貪心策略：
按左端點排序，從起點開始，每次選擇能延伸最遠的區間，逐步擴展覆蓋范圍。
十、區間分組問題
問題描述：
將一組區間分成若干個組，每組內的區間互不重疊，要求使用的組數最少。
貪心策略：
按左端點排序，使用最小堆維護各組的最早可用時間，優先將當前區間分配給最早空閑的組。
十一、任務調度問題
問題描述：
給定若干任務及其完成期限和利潤，選擇能獲得最大利潤的任務序列。
貪心策略：
按利潤降序排序，依次嘗試安排任務在最后可行的時間點。
十二、加油站問題
問題描述：
一輛車繞一圈油路，判斷是否可以從某一點出發完成一圈，并找出該起點。
貪心策略：
維護當前油量和總油量，若當前油量為負則重新設置起點。
十三、跳躍游戲
問題描述：
數組中每個元素代表可跳躍的最大步數，判斷是否可以到達最后一個位置。
貪心策略：
維護當前能跳到的最遠位置，逐步推進。
十四、跳躍游戲 II
問題描述：
在跳躍游戲中，求最少跳躍次數到達終點。
貪心策略：
維護當前能跳的最遠邊界，以及下一步的最遠可達。
?十五、股票買賣問題
問題描述：
允許多次買賣，但每次只能持有一股。
貪心策略：
只要第二天價格比今天高，就買入賣出。
十六、最小代價貪心問題
問題描述：
在有限操作次數內，通過優先選擇代價最低的操作使目標值最大化。
貪心策略：
按操作代價從小到大依次選擇操作，直到操作次數用盡。
1.https://codeforces.com/contest/2118/problem/C
思路：
? ? ? ? 統計每個數字每一位變1的代價，排序取最小的 n 個即可。
代碼：
void solve()
{ll n, k;cin >> n >> k;vector<ll> a(n + 10);cin >> a;vector<ll> v;ll ans = 0;for (ll i = 0; i < n; ++i){ll x = a[i];ll cnt = 0;for (ll j = 0; j < 63; ++j){if (x >> j & 1ll)ans++;elsev.pb(1ll << j);}}sort(all(v));for (auto x : v){if (k <= 0)break;if (k >= x){ans++;k -= x;}}cout << ans << endl;
}2.https://codeforces.com/contest/1722/problem/D
思路：
? ? ? ? 統計每個字符最大貢獻與當前貢獻的差值，排序即可。
代碼：
void solve()
{int n;string s;cin >> n >> s;s = ' ' + s;ll ans = 0;vector<int> maxx(n + 10, 0);for (int i = 1; i <= n; ++i){if (s[i] == 'L'){maxx[i] = {abs(max(i - 1, (n - i)) - (i - 1))};ans += i - 1;}else{maxx[i] = {abs(max(i - 1, (n - i)) - (n - i))};ans += n - i;}}sort(maxx.begin() + 1, maxx.begin() + 1 + n, greater<int>());for (int i = 1; i <= n; ++i){ans += maxx[i];cout << ans << ' ';}cout << endl;
}十七、其他
這類題目不是經典的貪心模型，但是解題思路是基于貪心策略的題目。
1.B-黃_牛客小白月賽118
思路：
? ? ? ? 每次配對 a[i] 和 a[i + 1]，如果不互質，就將 a[i + 1] 變為 1，因為 a[i] 在之前可能與其他的元素配對了，選擇修改 a[i + 1] 是更優的。
代碼：
void solve()
{int n;cin >> n;vector<ll> a(n + 10);for (int i = 0; i < n; ++i)cin >> a[i];ll ans = 0;for (int i = 0; i < n - 1; ++i){if (__gcd(a[i], a[i + 1]) != 1){a[i + 1] = 1;++ans;}}cout << ans << endl;
}2.https://codeforces.com/problemset/problem/2116/B
思路及代碼：cf2116B-CSDN博客
3.https://codeforces.com/problemset/problem/2067/B
思路及代碼：cf2067B-CSDN博客
4.https://codeforces.com/problemset/problem/2059/B
思路及代碼：cf2059B-CSDN博客
5.https://codeforces.com/contest/1760/problem/E
思路：
? ? ? ? 題目要求統計?且?
?的索引對數，由于只有 0、1 兩種元素，所以只需統計 1 后面有幾個 0 即可；我們還可以將 1 個元素取反，不難發現將第一個值為 0 的元素變 1 或最后一個值為1 的元素變 0 貢獻最大，可證明該貪心策略成立，由于數據量不大，直接把三種情況都統計一遍即可（不變的也要統計）。
代碼：
void solve()
{int n;cin >> n;vi a(n + 10), b;cin >> a;vi cnt1(n + 10, 0);int cur = 0;for (int i = n - 1; ~i; --i)if (a[i] == 0)++cur;elsecnt1[i] = cur;b = a;for (int i = 0; i < n; ++i)if (b[i] == 0){b[i] = 1;break;}vi cnt2(n + 10, 0);cur = 0;for (int i = n - 1; ~i; --i)if (b[i] == 0)++cur;elsecnt2[i] = cur;b = a;for (int i = n - 1; ~i; --i)if (b[i] == 1){b[i] = 0;break;}vi cnt3(n + 10, 0);cur = 0;for (int i = n - 1; ~i; --i)if (b[i] == 0)++cur;elsecnt3[i] = cur;ll ans1 = 0, ans2 = 0, ans3 = 0;for (int i = 0; i < n; ++i)ans1 += cnt1[i];for (int i = 0; i < n; ++i)ans2 += cnt2[i];for (int i = 0; i < n; ++i)ans3 += cnt3[i];cout << max({ans1, ans2, ans3}) << endl;
}
