C++演演算法學習之貪婪演演算法的應用

2022-05-25 18:01:33

貪心1

實驗題目：減肥的小K1

題目描述：

小K沒事幹，他要搬磚頭，為了達到較好的減肥效果，教練規定的方式很特別：每一次，小K可以把兩堆磚頭合併到一起，消耗的體力等於兩堆磚頭的重量之和。經過 n-1次合併後，就只剩下一堆了。小K在搬磚頭時總共消耗的體力等於每次合併所耗體力之和。小K為了偷懶，希望耗費的體力最小。例如有 3堆磚頭，數目依次為 1、2、9 。可以先將 1 、 2 堆合併，新堆數目為3 ，耗費體力為 3 。接著，將新堆與原先的第三堆合併，又得到新的堆，數目為 12 ，耗費體力為12 。所以總共耗費體力 =3+12=15。可以證明 15為最小的體力耗費值。

輸入要求：

共兩行。

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

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

輸出要求：

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

實驗程式碼及註釋:

#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為第三個的下標
        while (a[k] < temp && k < n) {//比較第三個和前兩個的和，若第三個比前兩個要小
            a[k - 1] = a[k];//前移
            k++;
        }
        a[k - 1] = temp;
        sum += temp;
    }
    cout << sum << endl;
    return 0;
}

演演算法分析與知識點：

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

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

實驗題目：最小跳數

題目描述：

給定一個非負整數陣列，假定你的初始位置為陣列第一個位置。陣列中的每個元素代表你在那個位置能夠跳躍的最大長度。你的目標是到達最後一個下標位置，並且使用最少的跳躍次數。

輸入要求：

輸入一組非負整數陣列，陣列長度不超過500。

輸出要求：

最少經過幾次跳躍，可以到達最後一個位置。

實驗程式碼及註釋:

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

}

演演算法分析與知識點：

本題主要運用貪心的思想，在具體的實現中，我們維護當前能夠到達的最大下標位置，記為邊界。我們從左到右遍歷陣列，到達邊界時，更新邊界並將跳躍次數增加 1。

在遍歷陣列時，我們不存取最後一個元素，這是因為在存取最後一個元素之前，我們的邊界一定大於等於最後一個位置，否則就無法跳到最後一個位置了。如果存取最後一個元素，在邊界正好為最後一個位置的情況下，我們會增加一次「不必要的跳躍次數」，因此我們不必存取最後一個元素。

實驗題目：排隊接水

題目描述：

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

輸入要求：

輸入有多組測試資料

每組測試資料共兩行，第一行為一個整數n，表示有n個人；

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

輸出要求：

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

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

實驗程式碼及註釋:

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

bool cmp(person p1, person p2) { // 自定義結構體排序方法
	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("%.2fn", ans / n);
	}
	return 0;

}

演演算法分析與知識點：

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

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

貪心-堂練

實驗題目：區間問題1

題目描述：

給出n個區間的起點和終點，求最少使用其中多少個區間可以將所有區間所在的區域完全覆蓋。（測試的資料確保這1點）。

輸入要求：

第1行一個整數n，表示n個區間；

第2行開始n行，每行2個整數，表示一個區間範圍。

類似[1,4] [5,6]被認為是覆蓋了[1,6]。

輸出要求：

從起點開始，按區間先後順序，輸出選中的區間。所選的區間應儘可能向終點擴充套件。

實驗程式碼及註釋:

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

struct part//區間兩端
{
	int star1, end1;
};

bool cmp(part s1, part s2) { // 自定義排序方式1、開始點升序，2、結束點升序
	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];//全部待選區間
	part r[100];
	//在a中選好的數放入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; // 待覆蓋區間最遠處


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


		while (a[i].star1 <= right + 1 && i < n) { // 尋找最遠子區間
			if (a[i].end1 > maRight) {
				maRight = a[i].end1;
				maIndex = i;
			}
			i++;  //比較完陣列往後移
		}
		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;
}

演演算法分析與知識點：

思路：設定一個a[]陣列儲存原始的資料，設定一個人r[]陣列儲存被選的區間資料。

先按1、開始點升序，2、結束點升序將資料排序。為了使覆蓋總區間的所需的子區間數最少，就要選出一系列覆蓋範圍最廣的子區間。方式描述如下所示：初始令所能到達的範圍為，然後選出一個子區間讓這個範圍儘可能向區間終點靠，即找到符合條件的最遠子區間。

實驗題目：種樹

題目描述：

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

輸入要求：

第一行包含資料N，區域的個數；

第二行包含H，房子的數目；

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

輸出要求：

輸出能滿足所有要求的最少的樹的數。

實驗程式碼及註釋:

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

int n, m, k, ans;
struct node // 儲存要求資料
{
	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++) // 輸入資料
	{
		cin >> a[i].b >> a[i].e >> a[i].t;
	}
	sort(a, a + m, cmp);
	memset(used, 0, sizeof(used)); //初始化每個位置都沒種過樹
	ans = 0; // 記錄所需樹的數量
	for (int i = 0;i < m;i++)
	{
		k = 0;
		for (int j = a[i].b;j <= a[i].e;j++) // 求在該要求區間內已經種了多少樹
		{
			if (used[j]) k++;
		}
		if (k >= a[i].t) // 未達到要求
			continue;
		k = a[i].t - k;  // 還要種的數量
		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;
}

演演算法分析與知識點：

本題採用貪婪演演算法的思想，要使所需的總樹苗數量最小，就要讓一個區間的樹苗將可能的能滿足更多的使用者要求。這裡採用讓後面的居民儘可能為前面的居民著想，即在滿足自己要求的前提下把樹儘可能地往前面的位置種，這樣可以讓居民的要求重疊的範圍更多，從而達到使用最少的樹苗滿足所有居民的要求。

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

實驗題目：智力大沖

題目描述：

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

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

輸入要求：

輸入文共4行。

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

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

第3行有n個數，分別表示遊戲1到n的規定完成期限；

第4行有n個數，分別表示遊戲1到n不能在規定期限前完成的扣款數。

輸出要求：

輸出僅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;
}

演演算法分析與知識點：

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

實驗題目：刪除數位II

題目描述：

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

輸入要求：

輸入有一行，先輸入數位串m，再輸入k，如描述所示。

保證數位串m沒有前導0。

輸出要求：

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

第二行輸出刪除k個數位後剩下的數位組成的新數，並換行。

實驗程式碼及註釋:

#include <bits/stdc++.h>
using namespace std;
struct node // 記錄被刪除數位的內容及下標
{
    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; //下標陣列
    cin >> s >> k;
    for (int i = 0;i < s.length();i++) //初始化下標陣列
        index.push_back(i);
    for (int i = 0;i < k;i++) {
        int j;
        for (j = 0;j < s.length() - 1;j++) { // 尋找要刪除哪個數位
            if (s[j] > s[j + 1]) {
                break;
            }
        }
        temp[i].c = s[j]; // 記錄被刪除數位的內容
        temp[i].index = index[j]; // 記錄被刪除數位在原數位中的位置
        s.erase(j, 1);
        index.erase(index.begin() + j);
    }
    sort(temp, temp + k, cmp);//將刪除的數位按其在原數位中的位置排序
    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個數位的中的數位字串後數位最大，就要讓每次刪除一個字元后留下來的數位都要是當下的最小值。

為了找到一個字元，將其刪除後讓留下來的數位最小，被刪除的數位要滿足條件如下：

從數位字串從高位到低位第一個變小的數位。