C++實(shí)現(xiàn)貪心算法的示例詳解
區(qū)間問(wèn)題
區(qū)間選點(diǎn)
給定 N 個(gè)閉區(qū)間 [ai,bi],請(qǐng)你在數(shù)軸上選擇盡量少的點(diǎn),使得每個(gè)區(qū)間內(nèi)至少包含一個(gè)選出的點(diǎn)。
輸出選擇的點(diǎn)的最小數(shù)量。
位于區(qū)間端點(diǎn)上的點(diǎn)也算作區(qū)間內(nèi)。
輸入格式
第一行包含整數(shù) N,表示區(qū)間數(shù)。
接下來(lái) N 行,每行包含兩個(gè)整數(shù) ai,bi,表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù),表示所需的點(diǎn)的最小數(shù)量。
數(shù)據(jù)范圍
1≤N≤1e5,
−1e9≤ai≤bi≤1e9
先對(duì)右端點(diǎn)進(jìn)行排序,有交集的區(qū)間進(jìn)行右端點(diǎn)的更新,沒(méi)有交集則點(diǎn)數(shù)+1。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct node{ int a,b; bool operator<(const node&w)const { return b<w.b;} }range[N]; int main(){ int n; cin>>n; int a,b; for(int i=0;i<n;i++){ cin>>a>>b; range[i]={a,b}; } sort(range, range+n); int s=-2e9,cnt=0; for(int i=0;i<n;i++){ if(s<range[i].a){ cnt++; s=range[i].b; } } cout<<cnt; return 0; }
最大不相交區(qū)間數(shù)量
給定 N 個(gè)閉區(qū)間 [ai,bi],請(qǐng)你在數(shù)軸上選擇若干區(qū)間,使得選中的區(qū)間之間互不相交(包括端點(diǎn))。
輸出可選取區(qū)間的最大數(shù)量。
輸入格式
第一行包含整數(shù) N,表示區(qū)間數(shù)。
接下來(lái) N 行,每行包含兩個(gè)整數(shù) ai,bi,表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù),表示可選取區(qū)間的最大數(shù)量。
數(shù)據(jù)范圍
1≤N≤1e5,
−1e9≤ai≤bi≤1e9
先對(duì)右端點(diǎn)進(jìn)行排序,有交集的區(qū)間進(jìn)行右端點(diǎn)的更新,沒(méi)有交集則點(diǎn)數(shù)+1。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct node{ int a,b; bool operator<(const node&w)const{ return b<w.b; } }range[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int a,b; cin>>a>>b; range[i]={a,b}; } int res=0,s=-2e9; sort(range,range+n); for(int i=0;i<n;i++){ if(range[i].a>s){ s=range[i].b; res++; } } cout<<res; return 0; }
區(qū)間分組
給定 N 個(gè)閉區(qū)間 [ai,bi],請(qǐng)你將這些區(qū)間分成若干組,使得每組內(nèi)部的區(qū)間兩兩之間(包括端點(diǎn))沒(méi)有交集,并使得組數(shù)盡可能小。
輸出最小組數(shù)。
輸入格式
第一行包含整數(shù) N,表示區(qū)間數(shù)。
接下來(lái) N 行,每行包含兩個(gè)整數(shù) ai,bi,表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù),表示最小組數(shù)。
數(shù)據(jù)范圍
1≤N≤1e5,
−1e9≤ai≤bi≤1e9
先區(qū)分左右端點(diǎn)進(jìn)行排序,再遍歷取左右 端點(diǎn)未抵消的最大值。
#include<bits/stdc++.h> using namespace std; const int N = 100010; int n; int b[2 * N], idx; int main() { cin >> n; for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; b[idx++] = l * 2; b[idx++] = r * 2 + 1;//用奇偶性區(qū)分左右端點(diǎn) } sort(b, b + idx); int res = 1, t = 0; for (int i = 0; i < idx; i++) { if (b[i] % 2 == 0)t++; else t--; res = max(res, t); } cout << res; return 0; }
優(yōu)先隊(duì)列做法。
#include<bits/stdc++.h> using namespace std; const int N = 100010; struct Range { int l, r; bool operator <(const Range& w)const { return l < w.l; } }range[N]; int n; int main() { cin >> n; for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; range[i] = { l,r };} sort(range, range + n); int res = 0,ed=-2e9; priority_queue<int, vector<int>, greater<int>>heap; for (int i = 0; i < n; i++) { auto r = range[i]; if (heap.empty() || heap.top() >= r.l)heap.push(r.r); else { int t = heap.top(); heap.pop(); heap.push(r.r); } } cout << heap.size(); return 0; }
區(qū)間覆蓋
給定 N 個(gè)閉區(qū)間 [ai,bi] 以及一個(gè)線(xiàn)段區(qū)間 [s,t],請(qǐng)你選擇盡量少的區(qū)間,將指定線(xiàn)段區(qū)間完全覆蓋。
輸出最少區(qū)間數(shù),如果無(wú)法完全覆蓋則輸出 −1。
輸入格式
第一行包含兩個(gè)整數(shù) s 和 t,表示給定線(xiàn)段區(qū)間的兩個(gè)端點(diǎn)。
第二行包含整數(shù) N,表示給定區(qū)間數(shù)。
接下來(lái) N 行,每行包含兩個(gè)整數(shù) ai,bi,表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù),表示所需最少區(qū)間數(shù)。
如果無(wú)解,則輸出 −1。
數(shù)據(jù)范圍
1≤N≤1e5,
−1e9≤ai≤bi≤1e9,
−1e9≤s≤t≤1e9
#include<bits/stdc++.h> using namespace std; const int N = 100010; struct Range { int l, r; bool operator <(const Range& w)const { return l < w.l; } }range[N]; int main() { int n; int st, ed; cin >> st >> ed; cin >> n; for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; range[i] = { l,r }; } sort(range, range + n); int res = 0; bool sc = false; for (int i = 0; i < n; i++) { int j = i, r = -2e9; while (j < n && range[j].l <= st) { r = max(r, range[j].r); j++; } if (r < st) { res = -1; break; } res++; if (r >= ed) { sc = true; break; } i = j-1; st = r; } if (!sc)cout << -1; else cout << res; return 0; }
Huffman樹(shù)
合并果子
在一個(gè)果園里,達(dá)達(dá)已經(jīng)將所有的果子打了下來(lái),而且按果子的不同種類(lèi)分成了不同的堆。
達(dá)達(dá)決定把所有的果子合成一堆。
每一次合并,達(dá)達(dá)可以把兩堆果子合并到一起,消耗的體力等于兩堆果子的重量之和。
可以看出,所有的果子經(jīng)過(guò) n−1 次合并之后,就只剩下一堆了。
達(dá)達(dá)在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。
因?yàn)檫€要花大力氣把這些果子搬回家,所以達(dá)達(dá)在合并果子時(shí)要盡可能地節(jié)省體力。
假定每個(gè)果子重量都為 1,并且已知果子的種類(lèi)數(shù)和每種果子的數(shù)目,你的任務(wù)是設(shè)計(jì)出合并的次序方案,使達(dá)達(dá)耗費(fèi)的體力最少,并輸出這個(gè)最小的體力耗費(fèi)值。
例如有 3 種果子,數(shù)目依次為 1,2,9。
可以先將 1、2 堆合并,新堆數(shù)目為 3,耗費(fèi)體力為 3。
接著,將新堆與原先的第三堆合并,又得到新的堆,數(shù)目為 12,耗費(fèi)體力為 12。
所以達(dá)達(dá)總共耗費(fèi)體力=3+12=15。
可以證明 15 為最小的體力耗費(fèi)值。
輸入格式
輸入包括兩行,第一行是一個(gè)整數(shù) n,表示果子的種類(lèi)數(shù)。
第二行包含 n 個(gè)整數(shù),用空格分隔,第 i 個(gè)整數(shù) ai 是第 i 種果子的數(shù)目。
輸出格式
輸出包括一行,這一行只包含一個(gè)整數(shù),也就是最小的體力耗費(fèi)值。
輸入數(shù)據(jù)保證這個(gè)值小于 231。
數(shù)據(jù)范圍
1≤n≤10000,
1≤ai≤20000
只需要用優(yōu)先隊(duì)列先取出兩個(gè),再插入一個(gè),直至最后剩下一個(gè)。
#include<iostream> #include<algorithm> #include<queue> #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; priority_queue<int, vector<int>, greater<int>>heap; while (n--) { int x; cin >> x; heap.push(x); } int res = 0; while (heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); int c = a + b; heap.push(c); res += c; } cout << res; return 0; }
排序不等式
排隊(duì)打水
有 n 個(gè)人排隊(duì)到 1 個(gè)水龍頭處打水,第 i 個(gè)人裝滿(mǎn)水桶所需的時(shí)間是 ti,請(qǐng)問(wèn)如何安排他們的打水順序才能使所有人的等待時(shí)間之和最小?
輸入格式
第一行包含整數(shù) n。
第二行包含 n 個(gè)整數(shù),其中第 i 個(gè)整數(shù)表示第 i 個(gè)人裝滿(mǎn)水桶所花費(fèi)的時(shí)間 ti。
輸出格式
輸出一個(gè)整數(shù),表示最小的等待時(shí)間之和。
數(shù)據(jù)范圍
1≤n≤1e5,
1≤ti≤1e4
值正序,下標(biāo)倒序相乘得到最小值
#include<bits/stdc++.h> using namespace std; const int N = 100010; int a[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int x=n; long long res=0; for (int i = 0; i < n; i++) { res += a[i] * (x - 1); x--; } cout << res; return 0; }
絕對(duì)值不等式
貨艙選址
在一條數(shù)軸上有 N 家商店,它們的坐標(biāo)分別為 A1∼AN。
現(xiàn)在需要在數(shù)軸上建立一家貨倉(cāng),每天清晨,從貨倉(cāng)到每家商店都要運(yùn)送一車(chē)商品。
為了提高效率,求把貨倉(cāng)建在何處,可以使得貨倉(cāng)到每家商店的距離之和最小。
輸入格式
第一行輸入整數(shù) N。
第二行 N 個(gè)整數(shù) A1∼AN。
輸出格式
輸出一個(gè)整數(shù),表示距離之和的最小值。
數(shù)據(jù)范圍
1≤N≤100000,
0≤Ai≤40000
只需統(tǒng)計(jì)各點(diǎn)到中位數(shù)的距離之和。
#include <bits/stdc++.h> using namespace std; const int N=100100; int a[N],n,i,ans,sum; int main() { cin>>n; for (i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n);//排序 int sm=a[n/2+1];//中位數(shù) for (i=1;i<=n;i++) ans=ans+abs(a[i]-sm);//統(tǒng)計(jì)和中位數(shù)之間的差 cout<<ans; return 0; }
以上就是C++實(shí)現(xiàn)貪心算法的示例詳解的詳細(xì)內(nèi)容,更多關(guān)于C++ 貪心算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
QT結(jié)合百度Ai實(shí)現(xiàn)車(chē)牌識(shí)別
當(dāng)下的人工智能勢(shì)頭很盛,本文主要介紹了QT結(jié)合百度Ai實(shí)現(xiàn)車(chē)牌識(shí)別,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-03-03C語(yǔ)言 鏈?zhǔn)蕉鏄?shù)結(jié)構(gòu)詳解原理
二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指,用鏈表來(lái)表示一棵二叉樹(shù),即用鏈來(lái)指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成,數(shù)據(jù)域和左右指針域,左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址2021-11-11C++使用智能指針實(shí)現(xiàn)模板形式的單例類(lèi)
這篇文章主要為大家詳細(xì)介紹了C++使用了智能指針實(shí)現(xiàn)模板形式的單例類(lèi),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-06-06C語(yǔ)言實(shí)現(xiàn)生成新春福字的示例詳解
這篇文章主要介紹了如何利用C語(yǔ)言實(shí)現(xiàn)生成各個(gè)字體的新春福字,再也不用擔(dān)心支付寶掃福找不到圖片了,感興趣的同學(xué)可以跟隨小編學(xué)習(xí)一下2022-01-01