---

一、概念

貪心是一種在每次決策時采取當(dāng)前意義下最優(yōu)策略的算法，因此，使用貪心法要求問題的整體最優(yōu)性可以由局部最優(yōu)性導(dǎo)出。貪心算法的正確性需要證明，常見的證明手段有:

1. 微擾(鄰項(xiàng)交換)
   1. 證明在任意局面下,任何對局部最優(yōu)策略的微小改變都會造成整體結(jié)果變差。經(jīng)常用于以“排序”為貪心策略的證明。
2. 范圍縮放
   1. 證明任何對局部最優(yōu)策略作用范圍的擴(kuò)展都不會造成整體結(jié)果變差
3. 決策包容性
   1. 證明在任意局面下,作出局部最優(yōu)決策以后,在問題狀態(tài)空間中的可達(dá)集合包含了作出其他任何決策后的可達(dá)集合。換言之,這個局部最優(yōu)策略提供的可能性包含其他所有策略提供的可能性。
4. 反證法
5. 數(shù)學(xué)歸納法

貪心算法在算法體系中較為特殊，這里通過幾道例題來體會貪心算法的應(yīng)用。

二、OJ練習(xí)

2.1 區(qū)間選點(diǎn)

區(qū)間選點(diǎn) - 45D - Codeforces

題目保證了有解，我們該如何選出可行解呢？

我們考慮把區(qū)間按照右端點(diǎn)升序排序，然后遍歷所有區(qū)間，對于每個區(qū)間選取區(qū)間內(nèi)沒有被選取的最左端點(diǎn)

如何證明正確性？——反證法

假設(shè)按照上述策略出現(xiàn)某個區(qū)間無點(diǎn)可選，該區(qū)間為[l, r]，說明有r - l + 1個右端點(diǎn)不小于l，不超過r的區(qū)間選擇了[l, r]內(nèi)的r - l + 1個點(diǎn)

它們選擇[l, r]內(nèi)的點(diǎn)說明它們在[0, l - 1]的部分都被選完了，否則按照靠左原則應(yīng)該選取[0, l - 1]的點(diǎn)，那么[l, r]內(nèi)就存在r - l + 2個區(qū)間的右端點(diǎn)，此時原問題無解，與題目條件矛盾，故策略正確。

對于區(qū)間問題通用操作是按照某端點(diǎn)排序，在處理區(qū)間問題沒有頭緒的時候可以試著排序來尋找突破口。

n = int(input())lines = []for _ in range(n):a, b = map(int, input().split())lines.append((a, b, _))
lines.sort(key=lambda x: x[1])st = set()
ans = [0] * n
for l, r, idx in lines:for i in range(l, r + 1):if not (i in st):st.add(i)ans[idx] = ibreakfor x in ans:print(x, end=' ')

2.2 區(qū)間合并

P2082 區(qū)間覆蓋（加強(qiáng)版） - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

即求區(qū)間合并后的長度

那么我們將區(qū)間按照左端點(diǎn)升序排序，然后順序遍歷區(qū)間

記錄當(dāng)前合并區(qū)間的左端點(diǎn)L，右端點(diǎn)R，對于遍歷到的區(qū)間[l, r]

如果l > R，那么說明和前面的區(qū)間不相交，我們累加前面區(qū)間的長度后更新當(dāng)前合并區(qū)間為[l, r]

否則，更新R = max(R, r)

證明很簡單，就是假設(shè)存在兩個可以合并的區(qū)間沒有合并，然后反證推出矛盾即可，不再贅述。

n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]
lines.sort(key=lambda x: x[0])res = 0
L, R = 0, -1
for x, y in lines:if x <= R:R = max(R, y)else:res += R - L + 1L, R = x, y
print(res + (R - L + 1))

2.3 區(qū)間

[P2434 SDOI2005] 區(qū)間 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

和上一道題做法一樣，是在上一道題目的基礎(chǔ)上加上了輸出具體方案

我們只需開一個數(shù)組表示當(dāng)前的不合并區(qū)間數(shù)組，如果當(dāng)前區(qū)間和最后一個不相交就加入數(shù)組，否則就維護(hù)最后一個區(qū)間的最右端點(diǎn)

n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]
lines.sort(key=lambda x: x[0])res = 0
ans = [lines[0]]
for x, y in lines:if x <= ans[-1][1]:ans[-1] = (ans[-1][0], max(ans[-1][1], y))else:ans.append((x, y))
for x, y in ans:print(x, y)

2.4 合并果子

148. 合并果子 - AcWing題庫

很明顯的貪心思路，每次區(qū)所有堆中最小的兩堆合并即可

為什么是正確的呢？

我們合并的過程其實(shí)可以構(gòu)造出一棵樹，這棵樹和Huffman樹其實(shí)是等價的。

上圖中藍(lán)色代表初始的果子堆，每個結(jié)點(diǎn)都是由兩個孩子合并而來

初始藍(lán)色結(jié)點(diǎn)的貢獻(xiàn)為深度 乘 結(jié)點(diǎn)權(quán)值

我們只需證明按照貪心策略得到的樹中：藍(lán)色結(jié)點(diǎn)的權(quán)值 * 深度之和最小即可

引理：權(quán)值最小的兩個點(diǎn)的深度一定最深，且互為兄弟

證明：如果不是，兩個點(diǎn)中至少有一個可以和最后一層的某個權(quán)值不小于自身的結(jié)點(diǎn)交換，那么兩個結(jié)點(diǎn)可以交換到最后一層并且成為兄弟，那么 藍(lán)色結(jié)點(diǎn)的權(quán)值 * 深度之和至少不會變大，甚至變小，故得證

那么最優(yōu)解的值等價于 權(quán)值最小的兩個點(diǎn)的值相加 加上 兩個點(diǎn)合并后與剩余的n - 2個點(diǎn)構(gòu)造出的最優(yōu)樹的值

同樣的，我們?nèi)绱说氯?#xff0c;可以構(gòu)造出一棵最優(yōu)解樹，故得證。

import heapq
n = int(input())
a = list(map(int, input().split()))
heapq.heapify(a)
res = 0
while len(a) > 1:x = heapq.heappop(a)y = heapq.heappop(a)res += x + yheapq.heappush(a, x + y)
print(res)

2.5 排隊(duì)接水

P1223 排隊(duì)接水 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

每個人接的越早，它的時間就會越多人忍受

所以我們讓接的少的人優(yōu)先接水即可

證明也很簡單，同樣反證，然后總可以按照貪心策略構(gòu)造出不比最優(yōu)解差甚至更優(yōu)的解

n = int(input())
a = [(int(x), _ + 1) for _, x in enumerate(input().split())]
a.sort()
s = 0
for i, (x, idx) in enumerate(a):s += x * (n - i - 1)print(idx, end=' ')
print('')
print('%.2f' % (s / n))

2.6 貨倉選址

104. 貨倉選址 - AcWing題庫

很經(jīng)典的中位數(shù)問題，就是數(shù)軸上找到一個點(diǎn)y使得，Σ|x - y|最小

上圖其實(shí)已經(jīng)很明白了，當(dāng)y選在兩個數(shù)里面的差絕對值和總小于等于在兩個數(shù)外面的差絕對值

那么我們剝洋蔥似的一層一層往里鉆，就會落到中位數(shù)處

n = int(input())
a = list(map(int, input().split()))
a.sort()mid = a[len(a) // 2]print(sum(abs(x - mid) for x in a))

2.7 防曬

110. 防曬 - AcWing題庫

又是區(qū)間問題，不過這道題按照左右端點(diǎn)哪個排都能做，其實(shí)有點(diǎn)讓每個資源發(fā)揮其最大作用的意思

怎么思考呢？我們把牛牛的區(qū)間按照右端點(diǎn)排序，然后順序遍歷牛牛每次選取在自己區(qū)間內(nèi)最小的那個防曬霜

如何證明我們這樣得到的一定是最優(yōu)解？

我們可以證明對任意最優(yōu)解按照貪心策略調(diào)整不會使得解變差從而得到一個最優(yōu)解，我們也可以用范圍縮放來證明，即我們的局部最優(yōu)貪心策略對整體影響最小。

我們已經(jīng)按照右端點(diǎn)排序，那么對于當(dāng)前枚舉奶牛的可用防曬霜x，y，SPF[x] < SPF[y]只有如下三種情況：

• 后面奶牛x，y都能用
• 后面奶牛只能用y
• 后面奶牛x，y都不能用

我們發(fā)現(xiàn)我們選擇x對后面奶牛影響最小，所以貪心策略正確。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 2510;int n, m;
PII w[N];
map<int, int> mp;int main(){cin >> n >> m;for(int i = 0; i < n; i ++) cin >> w[i].x >> w[i].y;for(int i = 0, a, b; i < m; i ++) cin >> a >> b, mp[a] += b;sort(w, w + n, [](const PII& a, const PII& b){return a.y < b.y;});int res = 0;for(int i = 0; i < n; i ++){ //cout << w[i].x << ' ' << w[i].y << endl;auto it = mp.lower_bound(w[i].x);if (it != mp.end() && it -> first <= w[i].y) {it -> second --, res ++;if(! it -> second) mp.erase(it);}}cout << res;return 0;
}

2.8 畜欄預(yù)定

111. 畜欄預(yù)定 - AcWing題庫

我們將牛按開始時間升序排序，然后枚舉牛

如果對于當(dāng)前牛有可以安排的畜欄（畜欄內(nèi)最后一頭牛結(jié)束時間不晚于當(dāng)前牛的開始時間），那么我們就安排進(jìn)去

如果沒有，就新開一個畜欄

上述做法的正確性：

反證法：我們存在不同于上述策略的方案為更優(yōu)解，只需m個畜欄，那么我們上述策略建立第m + 1個畜欄時，必然有m個畜欄的結(jié)束時間都大于當(dāng)前牛的開始時間，而由于我們按照開始時間升序，故m個畜欄的最后一頭牛都和當(dāng)前牛區(qū)間有交集，等價于m + 1頭牛兩兩有交集，所以我們至少需要m + 1個畜欄，矛盾，故得證。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define x first
#define y second
const int N = 5e4 + 10;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
PIII lines[N];
int n, id[N];
priority_queue<PII, vector<PII>, greater<PII>> pq;
int main(){cin >> n;for(int i = 0, a, b; i < n; i ++) cin >> a >> b, lines[i] = { {a, b}, i };sort(lines, lines + n);for(int i = 0; i < n; i ++){if(pq.empty() || pq.top().x >= lines[i].x.x)pq.emplace(lines[i].x.y, id[lines[i].y] = pq.size() + 1);else{PII t = pq.top();pq.pop();t.x = lines[i].x.y;pq.emplace(t);id[lines[i].y] = t.y;}}cout << pq.size() << endl;for(int i = 0; i < n; i ++) cout << id[i] << endl;return 0;
}

2.9 雷達(dá)設(shè)備

112. 雷達(dá)設(shè)備 - AcWing題庫

對于每個小島而言，可以覆蓋它的點(diǎn)對應(yīng)x軸上一個區(qū)間，那么每個小島就能夠有一個可監(jiān)測區(qū)間

我們只需選擇盡可能少的點(diǎn)使得每個區(qū)間都被覆蓋到即可，這就轉(zhuǎn)化為了區(qū)間選點(diǎn)問題

我們將區(qū)間按照右端點(diǎn)排序，然后如果當(dāng)前區(qū)間左端點(diǎn)小于覆蓋區(qū)間的右端點(diǎn)，說明該區(qū)間可以被前面覆蓋區(qū)間的點(diǎn)

否則我們就開一個新區(qū)間，所選的點(diǎn)為當(dāng)前區(qū)間的右端點(diǎn)

from math import sqrt
n, d = map(int, input().split())
eps = 1e-6
lines = []
for _ in range(n):x, y = map(int, input().split())if y - d > eps:print(-1)exit(0)dx = sqrt(d * d - y * y)lines.append((x - dx, x + dx))lines.sort(key=lambda x: x[1])
ed = -2000
res = 0
for l, r in lines:if l - ed > eps:res += 1ed = r
print(res)

2.10 國王游戲

114. 國王游戲 - AcWing題庫

本題貪心策略為：將大臣按照左手乘右手升序排序，此時的最大值最小

證明策略：臨項(xiàng)交換（微擾）

我們假設(shè)最優(yōu)解不是按照上述策略得到，那么一定存在a[i] * b[i] >= a[i + 1] * b[i + 1]

交換二者不影響其他大臣的收益

我們對比交換前后二者的收益：

交換前：i人：premul(i - 1) / bi i + 1人：premul(i - 1) * ai / bi+1

交換后：i人：premul(i - 1) / bi+1 i + 1人：premul(i - 1) * ai+1 / bi

四個數(shù)同乘 bi*bi+1/premul(i - 1):

交換前：i人：bi+1 i + 1人：ai bi

交換后：i人：bi i + 1人：ai+1 bi+1

由于ai * bi >= ai+1*bi+1，ai bi >= bi，則交換后整體的最大值沒有變大，甚至變小

那么我們交換所有逆序?qū)梢缘玫讲槐茸顑?yōu)解差的解，故我們的貪心策略正確。

cpp要手寫高精度

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;vector<int> mul(vector<int>& a, int x){int n = a.size(), t = 0;vector<int> ret;for(int i = 0; i < n; i ++){t += a[i] * x;ret.push_back(t % 10);t /= 10;}while(t) ret.push_back(t % 10), t /= 10;return ret;
}vector<int> div(vector<int>& a, int x){int n = a.size(), t = 0;vector<int> ret;for(int i = n - 1; ~i; i --){t = t * 10 + a[i];ret.push_back(t / x);t %= x;}reverse(ret.begin(), ret.end());while(ret.size() && !ret.back()) ret.pop_back();return ret;
}
vector<int> ma(const vector<int>& a, const vector<int>& b){if(a.size() > b.size()) return a;if(a.size() < b.size()) return b;if(vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;return b;
}
int n;
PII w[N];int main(){cin >> n, n ++;for(int i = 0, a, b; i < n; i ++) cin >> a >> b, w[i] = { a, b };sort(w + 1, w + n, [](const PII& a, const PII& b){return a.first * a.second < b.first * b.second;});vector<int> cur(1, 1), res(1, 0);for(int i = 0; i < n; i ++){ if(i)res = ma(res, div(cur, w[i].second));cur = mul(cur, w[i].first);/*for(int x : vector<int>(cur.rbegin(), cur.rend()))cout << x;puts("");*/} for(int x : vector<int>(res.rbegin(), res.rend()))cout << x;return 0;
}

不想寫高精度就用python3

n = int(input())
n += 1
w = [tuple(map(int, input().split())) for _ in range(n)]
cur ,res = w[0][0], 0
for a, b in sorted(w[1::], key=lambda x:x[0]*x[1]):res = max(res, cur // b)cur *= a
print(res)

2.11 耍雜技的牛

125. 耍雜技的牛 - AcWing題庫

和上一題很像，這題按照w + s升序排序

和上一題同樣的證明思路，不再贅述

n = int(input())
ws = [tuple(map(int, input().split())) for _ in range(n)]
pre = 0
ans = -1e18
for w, s in sorted(ws, key=lambda x:x[0]+x[1]):ans = max(ans, pre - s)pre += w
print(ans)

2.12 給樹染色

115. 給樹染色 - AcWing題庫

錯誤的貪心：從根結(jié)點(diǎn)開始擴(kuò)展，每次取當(dāng)前最小權(quán)值的結(jié)點(diǎn)

很容易舉出反例，可以自己試一下。

我們可以確定的事情是，當(dāng)前除去根節(jié)點(diǎn)的最大權(quán)值結(jié)點(diǎn)會在其父節(jié)點(diǎn)被染色后立即被染色。

那么我們考慮當(dāng)前最大結(jié)點(diǎn)x，父節(jié)點(diǎn)y，和任意結(jié)點(diǎn)z，染色順序無非：

x，y，z，代價為x + 2y + 3z

z，x，y，代價為：z + 2x + 3y

二者做差有：2z - (x + y)，可見當(dāng)z大于x+y的平均值時才會先染x+y

那么我們在考慮當(dāng)前樹中剩余結(jié)點(diǎn)時，不妨將x，y當(dāng)成一個結(jié)點(diǎn)，其權(quán)值為平均權(quán)值，然后就有了做法：

選擇當(dāng)前樹中的最大權(quán)值，進(jìn)行染色，由于它和父親染色順序?yàn)橐磺耙缓?#xff0c;所以染色后合并到父親結(jié)點(diǎn)后面

我們合并n - 1次就只剩下一個結(jié)點(diǎn)，此時整棵樹的染色順序也就知道了

具體實(shí)現(xiàn)時，由于我們并不關(guān)心具體染色方案，所以為了簡便，我們可以在合并時維護(hù)答案

考慮x合并到y(tǒng)上，由于要先染色y，所以x的權(quán)值要被加上y的sz次（sz為y結(jié)點(diǎn)的大小）

可以用并查集+堆優(yōu)化到O(nlogn)，不過這個數(shù)據(jù)量沒必要，重要的還是這道題的思想

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 1005;
const double eps = 1e-6;
struct node{int fa, sz, v;double avg;
}nodes[N];
int n, root, res;int nxt()
{double avg = 0;int res = -1;for (int i = 1; i <= n; i ++ )if (i != root && nodes[i].avg > avg){avg = nodes[i].avg;res = i;}return res;
}int main(){cin >> n >> root;for(int i = 1, v; i <= n; i ++){cin >> v, res += v;nodes[i] = { -1, 1, v, v };}for(int i = 1, a, b; i < n; i ++){cin >> a >> b;nodes[b].fa = a;}for(int i = 1; i < n; i ++){int t = nxt(), fa = nodes[t].fa;res += nodes[fa].sz * nodes[t].v;nodes[t].avg = -1;for(int j = 1; j <= n; j ++)if(nodes[j].fa == t) nodes[j].fa = fa;nodes[fa].sz += nodes[t].sz, nodes[fa].v += nodes[t].v, nodes[fa].avg = (double)nodes[fa].v / nodes[fa].sz;}cout << res;return 0;
}

2.13 任務(wù)

127. 任務(wù) - AcWing題庫

我們發(fā)現(xiàn)式子中x對于利潤占主導(dǎo)，所以按x從大到小來進(jìn)行考慮每個任務(wù)。對于每個任務(wù)從時間滿足的機(jī)器中選擇等級足夠且最小的那個。

具體流程如下：

• 按照x對任務(wù)和機(jī)器排序
• 按x從大到小遍歷任務(wù)，把時間充足的機(jī)器放入集合
• 如果集合中存在等級足夠的機(jī)器，那么選擇等級最小的那個
• 再處理下一個任務(wù)時，集合中的機(jī)器的時間都是足夠的，我們只需考慮等級

時間復(fù)雜度：O(nlogn + mlogn)

#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<int, int>;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m;
PII a[N], b[M];
int main(){std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);while (std::cin >> n >> m){for(int i = 0; i < n; i ++) std::cin >> a[i].first >> a[i].second;for(int i = 0; i < m; i ++) std::cin >> b[i].first >> b[i].second;std::sort(a, a + n), std::sort(b, b + m);std::multiset<int> st;i64 cnt = 0, res = 0;for(int i = m - 1, j = n - 1; ~i; i --){while(~j && a[j].first >= b[i].first)st.insert(a[j --].second);auto it = st.lower_bound(b[i].second);if(it != st.end()){cnt ++;res += 500 * b[i].first + 2 * b[i].second;st.erase(it);}}std::cout << cnt << ' ' << res << '\n';}return 0;
}

2.14 能量石

734. 能量石 - AcWing題庫

01背包 + 臨項(xiàng)交換

先暴力考慮所有情況，即全排列中依次求01背包

那么最優(yōu)解是否存在某種特性呢？或者說，我們需要考慮的情況的范圍能否縮小？

我們考慮最優(yōu)解，相鄰兩個能量石s[i], s[i + 1]

二者的收益為：e’[i] + e’[i + 1] - s[i] * l[i + 1]

交換次序：e’[i] + e’[i + 1] - s[i + 1] * l[i]

由于是最優(yōu)解，所以交換前的收益不小于交換后的收益：s[i] * l[i + 1] <= s[i + 1] * l[i]

那么說明最優(yōu)解滿足兩兩之間s[i] * l[i + 1] <= s[i + 1] * l[i]

所以我們將能量石按照s[i] / l[i]升序排序，然后跑01背包即可

#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
const int N = 105, M = 1e4 + 10;
struct node{int s, e, l;bool operator<(const node& x) const{return s * x.l < x.s * l;}
}nodes[N];int main(){int _ = 1;std::cin >> _;for(int t = 1, n, m; t <= _; t ++){std::cin >> n;m = 0;for(int i = 0, a, b, c; i < n; i ++) std::cin >> a >> b >> c, nodes[i] = { a, b, c }, m += a;std::sort(nodes, nodes + n);std::vector<i64> f(m + 1, -1e8);f[0] = 0;for(int i = 0; i < n; i ++){auto [s, e, l] = nodes[i];for(int j = m; j >= s; j --){f[j] = std::max(f[j], f[j - s] + e - (j - s) * l);}}printf("Case #%d: %lld\n", t, *std::max_element(f.begin(), f.end()));}return 0;
}

三、總結(jié)

很想從上面的問題中提取出某些東西，但是發(fā)現(xiàn)沒有套路可言，只是遇到貪心問題時有了幾個貪心的方向，區(qū)間類試著按端點(diǎn)排序，貪心構(gòu)造，臨項(xiàng)交換等等，但具體還得多做題。