C++實(shí)現(xiàn)貪心算法的示例詳解
區(qū)間問題
區(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ù)。
接下來 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)的更新，沒有交集則點(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ù)。
接下來 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)的更新，沒有交集則點(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)）沒有交集，并使得組數(shù)盡可能小。
輸出最小組數(shù)。
輸入格式
第一行包含整數(shù) N，表示區(qū)間數(shù)。
接下來 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è)線段區(qū)間 [s,t]，請(qǐng)你選擇盡量少的區(qū)間，將指定線段區(qū)間完全覆蓋。
輸出最少區(qū)間數(shù)，如果無法完全覆蓋則輸出 −1。
輸入格式
第一行包含兩個(gè)整數(shù) s 和 t，表示給定線段區(qū)間的兩個(gè)端點(diǎn)。
第二行包含整數(shù) N，表示給定區(qū)間數(shù)。
接下來 N 行，每行包含兩個(gè)整數(shù) ai,bi，表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù)，表示所需最少區(qū)間數(shù)。
如果無解，則輸出 −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樹
合并果子
在一個(gè)果園里，達(dá)達(dá)已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。
達(dá)達(dá)決定把所有的果子合成一堆。
每一次合并，達(dá)達(dá)可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。
可以看出，所有的果子經(jīng)過 n−1 次合并之后，就只剩下一堆了。
達(dá)達(dá)在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。
因?yàn)檫€要花大力氣把這些果子搬回家，所以達(dá)達(dá)在合并果子時(shí)要盡可能地節(jié)省體力。
假定每個(gè)果子重量都為 1，并且已知果子的種類數(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，表示果子的種類數(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è)人裝滿水桶所需的時(shí)間是 ti，請(qǐng)問如何安排他們的打水順序才能使所有人的等待時(shí)間之和最小？
輸入格式
第一行包含整數(shù) n。
第二行包含 n 個(gè)整數(shù)，其中第 i 個(gè)整數(shù)表示第 i 個(gè)人裝滿水桶所花費(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)送一車商品。
為了提高效率，求把貨倉(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)文章
今天小編就為大家分享一篇c語(yǔ)言 字符串的拼接和分割實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)中國(guó)象棋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
在我們?nèi)粘５纳钪忻總€(gè)人都或多或少存在一個(gè)"外號(hào)"，例如《西游記》中孫悟空就有諸多外號(hào)：美猴王，孫行者，齊天大圣等等。那么在C++中，也可以給一個(gè)已經(jīng)存在的變量取別名，這就是引用。那么接下來深入來探討一下引用2022-05-05
本文給大家分享的是作者在學(xué)習(xí)使用C++進(jìn)行編程的時(shí)候所用到的一些常用的軟件，這里推薦給大家2017-04-04
C++實(shí)現(xiàn)通訊錄管理系統(tǒng)項(xiàng)目
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)通訊錄管理系統(tǒng)項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章記錄一下串里面的模式匹配，模式匹配，顧名思義就是給定一個(gè)被匹配的字符串，然后用一個(gè)字符串模式（模型）去匹配上面說的字符串，看后者是否在前者里面出現(xiàn)。常用的有2種算法可以實(shí)現(xiàn)，下面我們來具體探討下2014-08-08
C++11 簡(jiǎn)單實(shí)現(xiàn)線程池的方法
這篇文章主要介紹了C++11 簡(jiǎn)單實(shí)現(xiàn)線程池的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
C++從文本文件讀取數(shù)據(jù)到vector中的方法
這篇文章主要給大家介紹了利用C++如何從文本文件讀取數(shù)據(jù)到vector中，文章通過實(shí)例給出示例代碼，相信會(huì)對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面來一起看看吧。2016-10-10
利用C++實(shí)現(xiàn)矩陣的相加/相稱/轉(zhuǎn)置/求鞍點(diǎn)
利用C++實(shí)現(xiàn)矩陣的相加/相稱/轉(zhuǎn)置/求鞍點(diǎn)。需要的朋友可以過來參考下，希望對(duì)大家有所幫助2013-10-10
這篇文章主要為大家介紹了C語(yǔ)言的循環(huán)小練習(xí)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01