C++算法學(xué)習(xí)之貪心算法的應(yīng)用

更新時間：2022年05月25日 14:21:36 作者：Andy-wen

貪心算法是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。本文為大家準(zhǔn)備了幾個示例，從而能深入了解貪心算法的應(yīng)用，需要的可以參考一下

貪心1

實驗題目：減肥的小K1

題目描述：

小K沒事干，他要搬磚頭，為了達(dá)到較好的減肥效果，教練規(guī)定的方式很特別：每一次，小K可以把兩堆磚頭合并到一起，消耗的體力等于兩堆磚頭的重量之和。經(jīng)過 n-1次合并后，就只剩下一堆了。小K在搬磚頭時總共消耗的體力等于每次合并所耗體力之和。小K為了偷懶，希望耗費的體力最小。例如有 3堆磚頭，數(shù)目依次為 1、2、9 ?？梢韵葘?1 、 2 堆合并，新堆數(shù)目為3 ，耗費體力為 3 。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 12 ，耗費體力為12 。所以總共耗費體力 =3+12=15?？梢宰C明 15為最小的體力耗費值。

輸入要求：

共兩行。

第一行是一個整數(shù) n(1≤n≤1000) ，表示磚頭堆數(shù)。

第二行n個整數(shù)，每個整數(shù)表示每堆磚頭的磚頭塊數(shù)。

輸出要求：

一個整數(shù)，也就是最小的體力耗費值。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, a[1000], sum = 0, i;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    for (i = 0; i < n - 1; i++) {
        int temp = a[i + 1] + a[i];//記錄前兩個最小的值
        int k = i + 2;//k為第三個的下標(biāo)
        while (a[k] < temp && k < n) {//比較第三個和前兩個的和，若第三個比前兩個要小
            a[k - 1] = a[k];//前移
            k++;
        }
        a[k - 1] = temp;
        sum += temp;
    }
    cout << sum << endl;
    return 0;
}

算法分析與知識點：

本題主要運用貪心的思想，每次都在全部磚頭中找到重量最輕的兩堆進行合并以達(dá)到最節(jié)約體力的目的。

因此要先對全部磚頭按重量進行排序，需要注意的是再合并完兩堆磚頭后需要對后續(xù)磚頭堆進行重新排序，第一次WA就是因為沒有對后續(xù)磚頭堆進行重新排序。

實驗題目：最小跳數(shù)

題目描述：

給定一個非負(fù)整數(shù)數(shù)組，假定你的初始位置為數(shù)組第一個位置。數(shù)組中的每個元素代表你在那個位置能夠跳躍的最大長度。你的目標(biāo)是到達(dá)最后一個下標(biāo)位置，并且使用最少的跳躍次數(shù)。

輸入要求：

輸入一組非負(fù)整數(shù)數(shù)組，數(shù)組長度不超過500。

輸出要求：

最少經(jīng)過幾次跳躍，可以到達(dá)最后一個位置。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 0, a[501];
    while (cin >> a[n++]);
    n = n - 1;
    // maxPos 記錄當(dāng)前最遠(yuǎn)能到哪里
    // step 記錄當(dāng)前進行了幾跳
    // end 記錄了當(dāng)前最遠(yuǎn)能到哪里的邊界
    int maxPos = 0, end = 0, step = 0;
    for (int i = 0;i < n - 1;i++) {
        if (maxPos >= i) { //判斷能否繼續(xù)探索
            maxPos = max(maxPos, i + a[i]);
            if (i == end) { // 到達(dá)邊界更新跳數(shù)
                end = maxPos;
                step++;
            }
        }
    }
    cout << step << endl;
    return 0;

}

算法分析與知識點：

本題主要運用貪心的思想，在具體的實現(xiàn)中，我們維護當(dāng)前能夠到達(dá)的最大下標(biāo)位置，記為邊界。我們從左到右遍歷數(shù)組，到達(dá)邊界時，更新邊界并將跳躍次數(shù)增加 1。

在遍歷數(shù)組時，我們不訪問最后一個元素，這是因為在訪問最后一個元素之前，我們的邊界一定大于等于最后一個位置，否則就無法跳到最后一個位置了。如果訪問最后一個元素，在邊界正好為最后一個位置的情況下，我們會增加一次「不必要的跳躍次數(shù)」，因此我們不必訪問最后一個元素。

實驗題目：排隊接水

題目描述：

夏天到了，又到了用水高峰期，偏巧小區(qū)的水管出了點問題，消防車趕緊給小區(qū)送了一車水過來。小區(qū)居民們紛紛拿出自家裝水的容器，有的是個大塑料瓶，有的是茶水壺，有的是小塑料桶，哈哈，什么樣的都有:)。現(xiàn)在有n個人在一個水龍頭前排隊接水，假設(shè)每個人接水的時間分別為Ti，請編程找出這n個人排隊的一種順序，使得這n個人的平均等待時間最小。

輸入要求：

輸入有多組測試數(shù)據(jù)

每組測試數(shù)據(jù)共兩行，第一行為一個整數(shù)n，表示有n個人；

第二行分別表示第1個人到第n個人每人的接水時間T1，T2,…Tn。

輸出要求：

輸出文件有兩行，第一行為一種排隊順序，即編號從1到n的n個人的一種排序方式；

第二行為這種排序方案下的平均等待時間（輸出結(jié)果精確到小數(shù)點后兩位）。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;
struct person // 定義居民結(jié)構(gòu)體，記錄到來順序及接水時間
{
	int id, time;
};
person p[1000];

bool cmp(person p1, person p2) { // 自定義結(jié)構(gòu)體排序方法
	return p1.time < p2.time;
}
int main() {
	int n;
	while (cin >> n) {
		for (int i = 0;i < n;i++) {
			p[i].id = i;
			cin >> p[i].time;
		}
		sort(p, p + n, cmp); // 按接水時間升序
		double ans = 0;
		for (int i = 0;i < n - 1;i++) {
			cout << p[i].id + 1 << " ";
			ans += (n - 1 - i) * p[i].time;
		}
		cout << p[n - 1].id + 1 << endl;
		printf("%.2f\n", ans / n);
	}
	return 0;

}

算法分析與知識點：

本題主要運用貪心的思想，共有n名居民，他們所需的接水時間分別為，設(shè)他們的排隊順序為，可得出總共等待時間為

由以上公式可得要使得總的排隊等待時間最短，就要按接水所需時間從小到大的順序老排隊接水。

貪心-堂練

實驗題目：區(qū)間問題1

題目描述：

給出n個區(qū)間的起點和終點，求最少使用其中多少個區(qū)間可以將所有區(qū)間所在的區(qū)域完全覆蓋。（測試的數(shù)據(jù)確保這1點）。

輸入要求：

第1行一個整數(shù)n，表示n個區(qū)間；

第2行開始n行，每行2個整數(shù)，表示一個區(qū)間范圍。

類似[1,4] [5,6]被認(rèn)為是覆蓋了[1,6]。

輸出要求：

從起點開始，按區(qū)間先后順序，輸出選中的區(qū)間。所選的區(qū)間應(yīng)盡可能向終點擴展。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;

struct part//區(qū)間兩端
{
	int star1, end1;
};

bool cmp(part s1, part s2) { // 自定義排序方式1、開始點升序，2、結(jié)束點升序
	if (s1.star1 < s2.star1)
		return true;
	else if (s1.star1 == s2.star1 && s1.end1 < s2.end1)
		return true;
	else
		return false;
}
int main()
{

	part a[100];//全部待選區(qū)間
	part r[100];
	//在a中選好的數(shù)放入r中

	int n, index = 0, i;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i].star1 >> a[i].end1;
	}

	sort(a, a + n, cmp);

	int right = a[0].star1 - 1;
	int end = a[n - 1].end1; // 待覆蓋區(qū)間最遠(yuǎn)處


	for (i = 0; i < n - 1; )
	{
		int maRight = a[i].end1, maIndex = i;


		while (a[i].star1 <= right + 1 && i < n) { // 尋找最遠(yuǎn)子區(qū)間
			if (a[i].end1 > maRight) {
				maRight = a[i].end1;
				maIndex = i;
			}
			i++;  //比較完數(shù)組往后移
		}
		right = maRight;
		r[index++] = a[maIndex];
		i = maIndex;
		if (right == end)
			break;
	}
	for (i = 0; i < index; i++) {
		cout << r[i].star1 << " " << r[i].end1 << endl;
	}
	return 0;
}

算法分析與知識點：

思路：設(shè)置一個a[]數(shù)組保存原始的數(shù)據(jù)，設(shè)置一個人r[]數(shù)組保存被選的區(qū)間數(shù)據(jù)。

先按1、開始點升序，2、結(jié)束點升序?qū)?shù)據(jù)排序。為了使覆蓋總區(qū)間的所需的子區(qū)間數(shù)最少，就要選出一系列覆蓋范圍最廣的子區(qū)間。方式描述如下所示：初始令所能到達(dá)的范圍為，然后選出一個子區(qū)間讓這個范圍盡可能向區(qū)間終點靠，即找到符合條件的最遠(yuǎn)子區(qū)間。

實驗題目：種樹

題目描述：

一條街的一邊有幾座房子。因為環(huán)保原因居民想要在路邊種些樹，路邊的地區(qū)被分割成塊，并被編號成1…N；每個部分為一個單位尺寸大小并最多可種一棵樹，每個居民想在門前種些樹并指定了三個號碼B,E,T，這三個數(shù)表示該居民想在B和E之間最少種T棵樹。當(dāng)然，B≤E,居民必須記住在指定區(qū)不能種多于區(qū)域地塊數(shù)的樹，所以T≤E-B+l。居民們想種樹的各自區(qū)域可以交叉。你的任務(wù)是求出能滿足所有要求的最少的樹的數(shù)量。

輸入要求：

第一行包含數(shù)據(jù)N，區(qū)域的個數(shù)；

第二行包含H，房子的數(shù)目；

下面的H行描述居民們的需要:B E T。

輸出要求：

輸出能滿足所有要求的最少的樹的數(shù)。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;

int n, m, k, ans;
struct node // 保存要求數(shù)據(jù)
{
	int b, e, t;
}a[5005];
bool used[30005]; // 記錄該位置是否種過樹

bool cmp(const node& a, const node& b) // 自定義排序方式
{
	return a.e < b.e;
}

int main()
{
	cin >> n >> m;
	for (int i = 0;i < m;i++) // 輸入數(shù)據(jù)
	{
		cin >> a[i].b >> a[i].e >> a[i].t;
	}
	sort(a, a + m, cmp);
	memset(used, 0, sizeof(used)); //初始化每個位置都沒種過樹
	ans = 0; // 記錄所需樹的數(shù)量
	for (int i = 0;i < m;i++)
	{
		k = 0;
		for (int j = a[i].b;j <= a[i].e;j++) // 求在該要求區(qū)間內(nèi)已經(jīng)種了多少樹
		{
			if (used[j]) k++;
		}
		if (k >= a[i].t) // 未達(dá)到要求
			continue;
		k = a[i].t - k;  // 還要種的數(shù)量
		for (int j = a[i].e;j >= a[i].b;j--)
		{
			if (used[j] == false) // 尋找沒種過的位置
			{
				used[j] = true;//種樹
				ans++;
				k--;
			}
			if (k == 0)
				break;
		}
	}
	cout << ans << endl;
	return 0;
}

算法分析與知識點：

本題采用貪心算法的思想，要使所需的總樹苗數(shù)量最小，就要讓一個區(qū)間的樹苗將可能的能滿足更多的用戶要求。這里采用讓后面的居民盡可能為前面的居民著想，即在滿足自己要求的前提下把樹盡可能地往前面的位置種，這樣可以讓居民的要求重疊的范圍更多，從而達(dá)到使用最少的樹苗滿足所有居民的要求。

為了達(dá)到目的，我們需要先將居民按提出要求的開始區(qū)間點排序，然后從后往前盡可能地為前面地居民考慮?？紤]滿足第i個居民方式：要先考慮滿足第i+1個居民的要求后里自己的要求還差多少，然后由于為第i-1個居民著想的目的，將未滿足要求的樹苗種在第i個居民要求區(qū)間的前面。

實驗題目：智力大沖

題目描述：

小偉報名參加中央電視臺的智力大沖浪節(jié)目，本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者m元。先不要太高興！因為這些錢還不一定都是你的！接下來主持人宣布了比賽規(guī)則：

首先，比賽時間分為n個時段(n≤500),它又給出了很多小游戲，每個小游戲都必須在規(guī)定期限ti前完成(1≤ti≤n)。如果一個游戲沒能在規(guī)定期限前完成，則要從獎勵費m元中扣去一部分錢wi，wi為自然數(shù)，不同的游戲扣去的錢是不一樣的。當(dāng)然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當(dāng)然更想贏取最多的錢！注意:比賽絕對不會讓參賽者賠錢！

輸入要求：

輸入文共4行。

第1行為m，表示一開始獎勵給每位參賽者的錢

第2行為n，表示有n個小游戲；

第3行有n個數(shù)，分別表示游戲1到n的規(guī)定完成期限；

第4行有n個數(shù)，分別表示游戲1到n不能在規(guī)定期限前完成的扣款數(shù)。

輸出要求：

輸出僅1行，表示小偉能贏取最多的錢。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, f[N];
struct node {
    int t, w;
}a[N];
int cmp(node x, node y) { return x.w > y.w; } // 自定義排序方式
void work()
{
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1;i <= n;i++)
    {
        bool pd = false;  // 判斷該游戲是否被完成
        for (int j = a[i].t;j >= 1;j--)
        {
            if (f[j] == 0) //可以安排這個游戲 
            {
                f[j] = 1;
                pd = true;
                break;
            }
        }
        if (pd == false) m -= a[i].w;
    }
}
int main()
{
    cin >> m >> n;
    for (int i = 1;i <= n;i++) cin >> a[i].t;
    for (int i = 1;i <= n;i++) cin >> a[i].w;
    work();
    cout << m << endl;
    return 0;
}

算法分析與知識點：

本題采用貪心算法的思想，首先將所有游戲按其價值從高到低排序。一個游戲只要在規(guī)定期限完成之前完成就不會被扣除獎勵，為了讓一個游戲盡可能不影響其他游戲，我們讓其在自己的規(guī)定期限內(nèi)盡可能地往后靠。我們從獎勵價值最高的游戲開始考慮，將所有游戲考慮完成后就可以得到的所獲得的獎勵最大值。

實驗題目：刪除數(shù)字II

題目描述：

在給定的n個數(shù)字的數(shù)字串m中，刪除其中k(k< n)個數(shù)字后，剩下的數(shù)字按原次序組成一個新的整數(shù)。請確定刪除方案，使得剩下的數(shù)字組成的新整數(shù)最小。(1<=k<n<=240)

輸入要求：

輸入有一行，先輸入數(shù)字串m，再輸入k，如描述所示。

保證數(shù)字串m沒有前導(dǎo)0。

輸出要求：

輸出有兩行，第一行按順序輸出從左到右刪除的k個數(shù)字，用空格隔開。（第一行里的輸出順序是按照被刪除數(shù)字在原數(shù)中的順序排列的，而不是按照刪除的順序排列的）

第二行輸出刪除k個數(shù)字后剩下的數(shù)字組成的新數(shù)，并換行。

實驗代碼及注釋:

#include <bits/stdc++.h>
using namespace std;
struct node // 記錄被刪除數(shù)字的內(nèi)容及下標(biāo)
{
    char c;
    int index;
}temp[300];
bool cmp(node a, node b) { // 自定義排序方式
    return a.index < b.index;
}
int main()
{
    string s, t;
    int k;
    vector<int> index; //下標(biāo)數(shù)組
    cin >> s >> k;
    for (int i = 0;i < s.length();i++) //初始化下標(biāo)數(shù)組
        index.push_back(i);
    for (int i = 0;i < k;i++) {
        int j;
        for (j = 0;j < s.length() - 1;j++) { // 尋找要刪除哪個數(shù)字
            if (s[j] > s[j + 1]) {
                break;
            }
        }
        temp[i].c = s[j]; // 記錄被刪除數(shù)字的內(nèi)容
        temp[i].index = index[j]; // 記錄被刪除數(shù)字在原數(shù)字中的位置
        s.erase(j, 1);
        index.erase(index.begin() + j);
    }
    sort(temp, temp + k, cmp);//將刪除的數(shù)字按其在原數(shù)字中的位置排序
    for (int i = 0;i < k - 1;i++)
        cout << temp[i].c << " ";
    cout << temp[k - 1].c << endl;
    while (s[0] == '0')
        s.erase(0, 1);
    if (s.length() == 0)
        s = "0";
    cout << s << endl;
    return 0;
}

算法分析與知識點：

本題采用貪心算法的思想，要刪除k個數(shù)字的中的數(shù)字字符串后數(shù)字最大，就要讓每次刪除一個字符后留下來的數(shù)字都要是當(dāng)下的最小值。

為了找到一個字符，將其刪除后讓留下來的數(shù)字最小，被刪除的數(shù)字要滿足條件如下：

從數(shù)字字符串從高位到低位第一個變小的數(shù)字。