C++算法學習之貪心算法的應用
貪心1
實驗題目：減肥的小K1
題目描述：
小K沒事干，他要搬磚頭，為了達到較好的減肥效果，教練規(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為第三個的下標
while (a[k] < temp && k < n) {//比較第三個和前兩個的和，若第三個比前兩個要小
a[k - 1] = a[k];//前移
k++;
}
a[k - 1] = temp;
sum += temp;
}
cout << sum << endl;
return 0;
}
算法分析與知識點：
本題主要運用貪心的思想，每次都在全部磚頭中找到重量最輕的兩堆進行合并以達到最節(jié)約體力的目的。
因此要先對全部磚頭按重量進行排序，需要注意的是再合并完兩堆磚頭后需要對后續(xù)磚頭堆進行重新排序，第一次WA就是因為沒有對后續(xù)磚頭堆進行重新排序。
實驗題目：最小跳數(shù)
題目描述：
給定一個非負整數(shù)數(shù)組，假定你的初始位置為數(shù)組第一個位置。數(shù)組中的每個元素代表你在那個位置能夠跳躍的最大長度。你的目標是到達最后一個下標位置，并且使用最少的跳躍次數(shù)。
輸入要求：
輸入一組非負整數(shù)數(shù)組，數(shù)組長度不超過500。
輸出要求：
最少經(jīng)過幾次跳躍，可以到達最后一個位置。
實驗代碼及注釋:
#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) { //判斷能否繼續(xù)探索
maxPos = max(maxPos, i + a[i]);
if (i == end) { // 到達邊界更新跳數(shù)
end = maxPos;
step++;
}
}
}
cout << step << endl;
return 0;
}
算法分析與知識點：
本題主要運用貪心的思想，在具體的實現(xiàn)中，我們維護當前能夠到達的最大下標位置，記為邊界。我們從左到右遍歷數(shù)組，到達邊界時，更新邊界并將跳躍次數(shù)增加 1。
在遍歷數(shù)組時，我們不訪問最后一個元素，這是因為在訪問最后一個元素之前，我們的邊界一定大于等于最后一個位置，否則就無法跳到最后一個位置了。如果訪問最后一個元素，在邊界正好為最后一個位置的情況下，我們會增加一次「不必要的跳躍次數(shù)」，因此我們不必訪問最后一個元素。
實驗題目：排隊接水
題目描述：
夏天到了，又到了用水高峰期，偏巧小區(qū)的水管出了點問題，消防車趕緊給小區(qū)送了一車水過來。小區(qū)居民們紛紛拿出自家裝水的容器，有的是個大塑料瓶，有的是茶水壺，有的是小塑料桶，哈哈，什么樣的都有:)?，F(xiàn)在有n個人在一個水龍頭前排隊接水，假設每個人接水的時間分別為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é)構體，記錄到來順序及接水時間
{
int id, time;
};
person p[1000];
bool cmp(person p1, person p2) { // 自定義結(jié)構體排序方法
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名居民，他們所需的接水時間分別為 ，設他們的排隊順序為 ，可得出總共等待時間為
由以上公式可得要使得總的排隊等待時間最短，就要按接水所需時間從小到大的順序老排隊接水。
貪心-堂練
實驗題目： 區(qū)間問題1
題目描述：
給出n個區(qū)間的起點和終點，求最少使用其中多少個區(qū)間可以將所有區(qū)間所在的區(qū)域完全覆蓋。（測試的數(shù)據(jù)確保這1點）。
輸入要求：
第1行一個整數(shù)n，表示n個區(qū)間；
第2行開始n行，每行2個整數(shù)，表示一個區(qū)間范圍。
類似[1,4] [5,6]被認為是覆蓋了[1,6]。
輸出要求：
從起點開始，按區(qū)間先后順序，輸出選中的區(qū)間。所選的區(qū)間應盡可能向終點擴展。
實驗代碼及注釋:
#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ū)間最遠處
for (i = 0; i < n - 1; )
{
int maRight = a[i].end1, maIndex = i;
while (a[i].star1 <= right + 1 && i < 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;
}
算法分析與知識點：
思路：設置一個a[]數(shù)組保存原始的數(shù)據(jù)，設置一個人r[]數(shù)組保存被選的區(qū)間數(shù)據(jù)。
先按1、開始點升序，2、結(jié)束點升序?qū)?shù)據(jù)排序。為了使覆蓋總區(qū)間的所需的子區(qū)間數(shù)最少，就要選出一系列覆蓋范圍最廣的子區(qū)間。方式描述如下所示：初始令所能到達的范圍為 ，然后選出一個子區(qū)間讓這個范圍盡可能向區(qū)間終點靠，即找到符合條件 的最遠子區(qū)間。
實驗題目：種樹
題目描述：
一條街的一邊有幾座房子。因為環(huán)保原因居民想要在路邊種些樹，路邊的地區(qū)被分割成塊，并被編號成1…N；每個部分為一個單位尺寸大小并最多可種一棵樹，每個居民想在門前種些樹并指定了三個號碼B,E,T，這三個數(shù)表示該居民想在B和E之間最少種T棵樹。當然，B≤E,居民必須記住在指定區(qū)不能種多于區(qū)域地塊數(shù)的樹，所以T≤E-B+l。居民們想種樹的各自區(qū)域可以交叉。你的任務是求出能滿足所有要求的最少的樹的數(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) // 未達到要求
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ū)間的樹苗將可能的能滿足更多的用戶要求。這里采用讓后面的居民盡可能為前面的居民著想，即在滿足自己要求的前提下把樹盡可能地往前面的位置種，這樣可以讓居民的要求重疊的范圍更多，從而達到使用最少的樹苗滿足所有居民的要求。
為了達到目的，我們需要先將居民按提出要求的開始區(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ù)，不同的游戲扣去的錢是不一樣的。當然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當然更想贏取最多的錢！注意:比賽絕對不會讓參賽者賠錢！
輸入要求：
輸入文共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沒有前導0。
輸出要求：
輸出有兩行，第一行按順序輸出從左到右刪除的k個數(shù)字，用空格隔開。（第一行里的輸出順序是按照被刪除數(shù)字在原數(shù)中的順序排列的，而不是按照刪除的順序排列的）
第二行輸出刪除k個數(shù)字后剩下的數(shù)字組成的新數(shù)，并換行。
實驗代碼及注釋:
#include <bits/stdc++.h>
using namespace std;
struct node // 記錄被刪除數(shù)字的內(nèi)容及下標
{
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; //下標數(shù)組
cin >> s >> k;
for (int i = 0;i < s.length();i++) //初始化下標數(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ù)字都要是當下的最小值。
為了找到一個字符，將其刪除后讓留下來的數(shù)字最小，被刪除的數(shù)字要滿足條件如下：
從數(shù)字字符串從高位到低位第一個變小的數(shù)字。
上述數(shù)字的第一次刪除就應該刪除數(shù)字8.
以上就是C++算法學習之貪心算法的應用的詳細內(nèi)容，更多關于C++貪心算法的資料請關注腳本之家其它相關文章！
相關文章
在本篇文章里小編給大家整理的是一篇關于C字符串函數(shù)對應的C++ string操作知識點內(nèi)容，有興趣的朋友們學習下。2020-01-01
本篇文章是對APUE 進程環(huán)境詳解進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C語言實現(xiàn)快速排序的方法及優(yōu)化,快速排序是Hoare于1962年提出的一種二叉樹結(jié)構的交換排序方法,下面我們來看一看傳說中的快速排序的特點與效率怎么樣,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了C++如何調(diào)用matlab函數(shù)的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-11-11
new和delete既是C++中的關鍵字也是一種特殊的運算符。這篇文章主要介紹了C++的new和delete詳解,需要的朋友可以參考下2018-02-02
C語言預處理是編程中非常重要的一個環(huán)節(jié),通過預處理指令和預處理器的一些特性,本文主要介紹了C語言中預處理命令的使用,具有一定的參考價值,感興趣的可以了解一下2024-02-02
下面小編就為大家?guī)硪黄獪\談C++阻止類被實例化詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-09-09![C++中delete和delete[]的區(qū)別](http://img.jbzj.com/images/xgimg/bcimg7.png)
這篇文章主要介紹了C++中delete和delete[]的區(qū)別的相關資料,需要的朋友可以參考下2016-03-03
程序中經(jīng)常需要將一組數(shù)據(jù)元素作為整體管理和使用，需要創(chuàng)建這種元素組，用變量記錄它們，傳進傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個數(shù)可能發(fā)生變化，順序表則是將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關系由它們的存儲順序自然表示2022-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)倉庫物資管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12