C++算法學習之貪心算法的應用
貪心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("%.2f\n", 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個數字的中的數字字符串後數字最大，就要讓每次刪除一個字符後留下來的數字都要是當下的最小值。
為瞭找到一個字符，將其刪除後讓留下來的數字最小，被刪除的數字要滿足條件如下：
從數字字符串從高位到低位第一個變小的數字。
上述數字的第一次刪除就應該刪除數字8.
以上就是C++算法學習之貪心算法的應用的詳細內容，更多關於C++貪心算法的資料請關註WalkonNet其它相關文章！