貪心1

實(shí)驗(yàn)題目：減肥的小K1

題目描述：

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

輸入要求：

共兩行。

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

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

輸出要求：

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

實(shí)驗(yà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];//記錄前兩個(gè)最小的值
        int k = i + 2;//k為第三個(gè)的下標(biāo)
        while (a[k] < temp && k < n) {//比較第三個(gè)和前兩個(gè)的和，若第三個(gè)比前兩個(gè)要小
            a[k - 1] = a[k];//前移
            k++;
        }
        a[k - 1] = temp;
        sum += temp;
    }
    cout << sum << endl;
    return 0;
}

算法分析與知識點(diǎn)：

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

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

實(shí)驗(yàn)題目：最小跳數(shù)

題目描述：

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

輸入要求：

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

輸出要求：

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

實(shí)驗(yàn)代碼及注釋:

#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)前進(jìn)行了幾跳
    // 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;

}

算法分析與知識點(diǎn)：

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

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

實(shí)驗(yàn)題目：排隊(duì)接水

題目描述：

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

輸入要求：

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

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

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

輸出要求：

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

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

實(shí)驗(yàn)代碼及注釋:

#include <bits/stdc++.h>
using namespace std;
struct person // 定義居民結(jié)構(gòu)體，記錄到來順序及接水時(shí)間
{
	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); // 按接水時(shí)間升序
		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;

}

算法分析與知識點(diǎn)：

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

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

貪心-堂練

實(shí)驗(yàn)題目： 區(qū)間問題1

題目描述：

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

輸入要求：

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

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

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

輸出要求：

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

實(shí)驗(yàn)代碼及注釋:

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

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

bool cmp(part s1, part s2) { // 自定義排序方式1、開始點(diǎn)升序，2、結(jié)束點(diǎn)升序
	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;
}

算法分析與知識點(diǎn)：

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

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

實(shí)驗(yàn)題目：種樹

題目描述：

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

輸入要求：

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

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

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

輸出要求：

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

實(shí)驗(yàn)代碼及注釋:

#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)); //初始化每個(gè)位置都沒種過樹
	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;
}

算法分析與知識點(diǎn)：

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

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

實(shí)驗(yàn)題目：智力大沖

題目描述：

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

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

輸入要求：

輸入文共4行。

第1行為m，表示一開始獎(jiǎng)勵(lì)給每位參賽者的錢

第2行為n，表示有n個(gè)小游戲；

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

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

輸出要求：

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

實(shí)驗(yàn)代碼及注釋:

#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) //可以安排這個(gè)游戲 
            {
                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;
}

算法分析與知識點(diǎn)：

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

實(shí)驗(yàn)題目：刪除數(shù)字II

題目描述：

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

輸入要求：

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

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

輸出要求：

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

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

實(shí)驗(yàn)代碼及注釋:

#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++) { // 尋找要?jiǎng)h除哪個(gè)數(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;
}

算法分析與知識點(diǎn)：

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

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

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

上述數(shù)字的第一次刪除就應(yīng)該刪除數(shù)字8.

以上就是C++算法學(xué)習(xí)之貪心算法的應(yīng)用的詳細(xì)內(nèi)容，更多關(guān)于C++貪心算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論