欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)貪心算法的示例詳解

 更新時(shí)間:2022年07月06日 08:17:31   作者:墻縫里的草  
這篇文章主要通過(guò)幾個(gè)試題為大家詳細(xì)介紹了C++中貪心算法的實(shí)現(xiàn),文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)貪心算法有一定的幫助,需要的可以參考一下

區(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í)別

    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-03
  • C++野指針和懸空指針的實(shí)現(xiàn)方法

    C++野指針和懸空指針的實(shí)現(xiàn)方法

    野指針和懸空指針是指針中常見(jiàn)的兩個(gè)概念,本文詳細(xì)的介紹了這兩種的使用,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • C++基于CMD命令行實(shí)現(xiàn)掃雷小游戲

    C++基于CMD命令行實(shí)現(xiàn)掃雷小游戲

    這篇文章主要為大家詳細(xì)介紹了C++基于CMD命令行實(shí)現(xiàn)掃雷小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • C++詳解如何實(shí)現(xiàn)單鏈表

    C++詳解如何實(shí)現(xiàn)單鏈表

    線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)又稱(chēng)為單鏈表,它是指通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素。本文將用C++實(shí)現(xiàn)單鏈表,需要的可以參考一下
    2022-06-06
  • 一文帶你簡(jiǎn)單了解c++正則表達(dá)式

    一文帶你簡(jiǎn)單了解c++正則表達(dá)式

    正則表達(dá)式在匹配字符串,驗(yàn)證輸入合法性時(shí)經(jīng)常用到.C++?11標(biāo)準(zhǔn)庫(kù)中已經(jīng)支持了正則表達(dá)式,下面這篇文章主要給大家介紹了關(guān)于c++正則表達(dá)式的相關(guān)資料,需要的朋友可以參考下
    2023-04-04
  • C語(yǔ)言 鏈?zhǔn)蕉鏄?shù)結(jié)構(gòu)詳解原理

    C語(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-11
  • C++ 指向類(lèi)成員的指針

    C++ 指向類(lèi)成員的指針

    指向類(lèi)成員的指針總的來(lái)講可以分為兩大類(lèi)四小類(lèi)(指向數(shù)據(jù)成員還是成員函數(shù),指向普通成員還是靜態(tài)成員)
    2020-03-03
  • C++使用智能指針實(shí)現(xiàn)模板形式的單例類(lèi)

    C++使用智能指針實(shí)現(xiàn)模板形式的單例類(lèi)

    這篇文章主要為大家詳細(xì)介紹了C++使用了智能指針實(shí)現(xiàn)模板形式的單例類(lèi),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • 純C語(yǔ)言:分治假幣問(wèn)題源碼分享

    純C語(yǔ)言:分治假幣問(wèn)題源碼分享

    這篇文章主要介紹了純C語(yǔ)言:分治假幣問(wèn)題源碼,有需要的朋友可以參考一下
    2014-01-01
  • C語(yǔ)言實(shí)現(xiàn)生成新春福字的示例詳解

    C語(yǔ)言實(shí)現(xiàn)生成新春福字的示例詳解

    這篇文章主要介紹了如何利用C語(yǔ)言實(shí)現(xiàn)生成各個(gè)字體的新春福字,再也不用擔(dān)心支付寶掃福找不到圖片了,感興趣的同學(xué)可以跟隨小編學(xué)習(xí)一下
    2022-01-01

最新評(píng)論