貪心算法~~

一、理論基礎

二、題目練習

（1）455. 分發餅干

（2）53. 最大子數組和 - 力扣

（3）122. 買賣股票的最佳時機 II - 力扣（LeetCode）

（4）860. 檸檬水找零 - 力扣（LeetCode）

（5）905. 區間選點 - AcWing題庫

?（6）AcWing 908. 最大不相交區間數量

?（7）906. 區間分組 - AcWing題庫

?（8）907. 區間覆蓋 - AcWing題庫

?（9）148. 合并果子 - AcWing題庫

?（10）913. 排隊打水 - AcWing題庫

（11）104. 貨倉選址 - AcWing題庫

一、理論基礎

貪心的本質是選擇每一階段的局部最優，從而達到全局最優。

????????例如，有一堆鈔票，你可以拿走十張，如果想達到最大的金額，你要怎么拿？

指定每次拿最大的，最終結果就是拿走最大數額的錢。

每次拿最大的就是局部最優，最后拿走最大數額的錢就是推出全局最優。

????????再舉一個例子如果是有一堆盒子，你有一個背包體積為n，如何把背包盡可能裝滿，如果還每次選最大的盒子，就不行了。這時候就需要動態規劃。

> 什么時候用貪心？

? ? ? ? hhh卡哥說沒有具體場景，，手動模擬一下感覺可以局部最優推出整體最優，而且想不到反例，那么就試一試貪心。貪心有時候就是常識性的推導，所以會認為本應該就這么做！

> 一般解題步驟？

將問題分解為若干個子問題
找出適合的貪心策略
求解每一個子問題的最優解
將局部最優解堆疊成全局最優解

確實過于理論化。。。。~一般都會涉及到排序、找規律、反證其可行性

?我們直接練題！！！

二、題目練習

（1）455. 分發餅干

????????局部最優就是大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個，全局最優就是喂飽盡可能多的小孩。

最終代碼：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {//給孩子和餅干排序sort(g.begin(),g.end());sort(s.begin(),s.end());int res=0;int index=s.size()-1;//將大餅干優先分給胃口大的孩子for(int i=g.size()-1;i>=0;i--)//遍歷胃口{if(index>=0&&s[index]>=g[i]) //遍歷餅干 {index--; //可以分配就指向下一個更大的餅干 res++;}}return res;}
};

?感覺還挺簡單的，難在找到他的局部最優性質

（2）53. 最大子數組和 - 力扣

解法一：可以暴力，但是時間復雜度會高

?解法二：dp,之前我們有做過~

解法三：貪心

????????如果 -2 1 在一起，計算起點的時候，一定是從 1 開始計算，因為負數只會拉低總和，這就是貪心貪的地方！局部最優：當前“連續和”為負數的時候立刻放棄，從下一個元素重新計算“連續和”，因為負數加上下一個元素 “連續和”只會越來越小。

遍歷 nums，從頭開始用 count 累積，如果 count 一旦加上 nums[i]變為負數，那么就應該從 nums[i+1]開始從 0 累積 count 了，因為已經變為負數的 count，只會拖累總和。

class Solution {
public:int maxSubArray(vector<int>& nums) {int res=INT_MIN; //一個很小的負數int cnt=0;for(int i=0;i<nums.size();i++){cnt+=nums[i];if(cnt>res)res=cnt;if(cnt<=0) cnt=0; //加上之后非正了，cnt=0相當于重置最大子序起始位置}return res;}
};

（3）122. 買賣股票的最佳時機 II - 力扣（LeetCode）

在dp中我們也做過這道題~~，找到局部最優性質后，用貪心更簡單一點?

局部最優：收集每天的正利潤，全局最優：求得最大利潤。

是不是特別簡單哈哈哈

class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for (int i = 1; i < prices.size(); i++) {result += max(prices[i] - prices[i - 1], 0);}return result;}
};

（4）860. 檸檬水找零 - 力扣（LeetCode）

只需要維護三種金額的數量，5，10和20。

情況一：賬單是5，直接收下。
情況二：賬單是10，消耗一個5，增加一個10
情況三：賬單是20，優先消耗一個10和一個5，如果不夠，再消耗三個5

賬單是20的情況，為什么要優先消耗一個10和一個5呢？

????????因為美元10只能給賬單20找零，而美元5可以給賬單10和賬單20找零，美元5更萬能！

所以局部最優：遇到賬單20，優先消耗美元10，完成本次找零。全局最優：完成全部賬單的找零。

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0, twenty = 0;for (int bill : bills) {// 情況一if (bill == 5) five++;// 情況二if (bill == 10) {if (five <= 0) return false; //找不了ten++;five--;}// 情況三if (bill == 20) {// 優先消耗10美元，因為5美元的找零用處更大，能多留著就多留著if (five > 0 && ten > 0) {five--;ten--;twenty++; // 其實這行代碼可以刪了，因為記錄20已經沒有意義了，不會用20來找零} else if (five >= 3) {five -= 3;twenty++; // 同理，這行代碼也可以刪了} else return false;}}return true;}
};

（5）905. 區間選點 - AcWing題庫

?數軸上有一些區間，在數軸上選取幾個點，要求每個區間上最少有一個點。

?????

? ? ? ??

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{int l, r; //左右結點bool operator< (const Range &W)const{return r < W.r; //按照右端點從小到大排序}
}range[N];int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) cin>>range[i].l>>range[i].r;sort(range, range + n);int res = 0, ed = -2e9;for (int i = 0; i < n; i ++ )if (ed < range[i].l) //新的左端點不能覆蓋右端點{res ++ ; //需要新增一個結點ed = range[i].r; //更新右端點}cout<<res;return 0;
}

?（6）AcWing 908. 最大不相交區間數量

?與上一道區間選點的題一樣，一定要是對右端點從小到大排序！！！！

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{int l, r; //左右結點bool operator< (const Range &W)const{return r < W.r; //按照右端點從小到大排序}
}range[N];int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) cin>>range[i].l>>range[i].r;sort(range, range + n);int res = 0, ed = -2e9;for (int i = 0; i < n; i ++ )if (ed < range[i].l) //新的左端點不能覆蓋右端點{res ++ ; //需要新增一個結點ed = range[i].r; //更新右端點}cout<<res;return 0;
}

?（7）906. 區間分組 - AcWing題庫

?等效于把盡可能多的區間塞進同一組，要滿足range[i].l > heap.top

把所有區間按照左端點從小到大排序
從前往后枚舉每個區間，判斷此區間能否將其放到現有的組中
heap有多少區間，就有多少組

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{int l, r;bool operator< (const Range &W)const{return l < W.l; //按照左端點排序！！！！}
}range[N];int main()
{cin>>n;for (int i = 0; i < n; i ++ ){int l, r;cin>>l>>r;range[i] = {l, r};}sort(range, range + n);//小根堆（每次彈出最小的數）--每個組的右端點存儲在 heap 中priority_queue<int, vector<int>, greater<int>> heap;for (int i = 0; i < n; i ++ ){//新區間的左端點大于等于堆頂的右端點if (heap.empty() || heap.top() >= range[i].l){heap.push(range[i].r); //開一個新組，記錄其右端點}else { //可以合并heap.pop();//取出右端點最小的區間heap.push(range[i].r);//保留這個右端點較大的區間}}cout<<heap.size();return 0;
}

?（8）907. 區間覆蓋 - AcWing題庫

?

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e9+10;
#define PII pair<int ,int>
PII a[N];
int s,t,n;
int main()
{cin>>s>>t;cin>>n;for(int i=0;i<n;i++){cin>>a[i].first>>a[i].second;}sort(a,a+n);int res=0;bool flag=false;//默認無法完全覆蓋for(int i=0;i<n;i++){int j=i,r=-M;while(j<n&&a[j].first<=s){r=max(r,a[j].second);j++;}if(r<s) {res=-1;break;}res++;//最后更新的右端點大于給定區間---能覆蓋if(r>=t) {flag=true;break;}s=r;//每次更新左端點為能覆蓋給定區間的最大的右端點i=j-1;}if(!flag) res=-1;cout<<res;return 0;}

?（9）148. 合并果子 - AcWing題庫

在學優先隊列的時候做過這道題~~

priority_queue 優先隊列-CSDN博客

#include<bits/stdc++.h>
using namespace std;
using ll =long long;
ll ans;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin>>n;priority_queue<ll,vector<ll>,greater<ll>> pq;while(n--){ll x;cin>>x;pq.push(x);}while(pq.size()>=2){ll x=pq.top();pq.pop();ll y=pq.top();pq.pop();ans+=x+y;pq.push(x+y);}cout<<ans;return 0;
}

?（10）913. 排隊打水 - AcWing題庫

需要將打水時間最短的人先打水 --計算前綴和數組的和（不包含最后一個人）

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int main()
{int n;cin>>n;vector<LL> a(n+1);vector<LL> qz(n+1,0);//前綴和數組for(int i=1;i<=n;i++) cin>>a[i];//從小到大排序sort(a.begin(),a.end());//計算排序后的前綴和數組（不用計算最后一個）for(int i=1;i<n;i++) qz[i]=qz[i-1]+a[i];//求前綴和的sumcout<<accumulate(qz.begin()+1,qz.end(),0ll);return 0;
}

（11）104. 貨倉選址 - AcWing題庫

貪心策略：一開始自己也猜到了哈哈哈就是中位數

?排序 +中位數

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{cin>>n;for (i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);//排序int sm=a[n/2+1];//中位數for (i=1;i<=n;i++)ans=ans+abs(a[i]-sm);//統計和中位數之間的差cout<<ans;return 0;
}