求生之路2怎么做非官方網(wǎng)站東莞做網(wǎng)站公司
文章目錄
- 一、概念
- 二、OJ練習(xí)
- 2.1 區(qū)間選點(diǎn)
- 2.2 區(qū)間合并
- 2.3 區(qū)間
- 2.4 合并果子
- 2.5 排隊(duì)接水
- 2.6 貨倉選址
- 2.7 防曬
- 2.8 畜欄預(yù)定
- 2.9 雷達(dá)設(shè)備
- 2.10 國王游戲
- 2.11 耍雜技的牛
- 2.12 給樹染色
- 2.13 任務(wù)
- 2.14 能量石
- 三、總結(jié)
一、概念
貪心是一種在每次決策時采取當(dāng)前意義下最優(yōu)策略的算法,因此,使用貪心法要求問題的整體最優(yōu)性可以由局部最優(yōu)性導(dǎo)出。貪心算法的正確性需要證明,常見的證明手段有:
- 微擾(鄰項(xiàng)交換)
- 證明在任意局面下,任何對局部最優(yōu)策略的微小改變都會造成整體結(jié)果變差。經(jīng)常用于以“排序”為貪心策略的證明。
- 范圍縮放
- 證明任何對局部最優(yōu)策略作用范圍的擴(kuò)展都不會造成整體結(jié)果變差
- 決策包容性
- 證明在任意局面下,作出局部最優(yōu)決策以后,在問題狀態(tài)空間中的可達(dá)集合包含了作出其他任何決策后的可達(dá)集合。換言之,這個局部最優(yōu)策略提供的可能性包含其他所有策略提供的可能性。
- 反證法
- 數(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)交換等等,但具體還得多做題。