本文主要是介绍Peter算法小课堂—贪心算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
课前思考：贪心是什么？贪心如何“贪”？
课前小视频：什么是贪心算法 - 知乎 (zhihu.com)
贪心
贪心是一种寻找最优解问题的常用方法。
贪心一般将求解过程分拆成若干个步骤，自顶向下，解决问题
太戈编程第1377题 抓娃娃
题目描述：
你有一台抓娃娃机器，玩法有点特别：机器会随机给你一排N个娃娃（1≤N≤100），编号1到N，但是顺序已经打乱了，你需要把他们重新排序变成1号到N号递增。
每一次你可以抓起最左边的娃娃沿着队伍向后移动到k个娃娃后的位置，k可以是范围1…N−1中的任意数。每次操作只能对最左边娃娃操作，不能对其他娃娃操作。
例如，假设N=4，娃娃开始时是这样的顺序：
4, 3, 2, 1
现在唯一可以移动的娃娃是4号。当把它向队伍后移动2步之后，队伍的顺序会变成：
3, 2, 4, 1
现在唯一可以移动的娃娃是3号，如此进行直到娃娃们排好了顺序。
请求出将娃娃们排好顺序所需要的最小操作次数。
举例子，找规律
经过几小时的找规律，我们会发现……
所以说呢……
如果排列最后有连续最多k个数严格上升，则最少移动次数为n-k!
上代码八
#include <bits/stdc++.h>
using namespace std;
int n,a[105];
int main(){freopen("doll.in","r",stdin);freopen("doll.out","w",stdout);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=n-1;for(int i=n-1;i>=1;i--){if(a[i]<a[i+1]) ans--;else break;}cout<<ans<<endl;return 0;
}太戈编程第1423题 大堵车1
题目描述：
在一条无限长的直线公路上，有n辆车正在从左向右行驶。每辆车的当前位置各不相同，各自的速度也可能不同。因为只有一条车道，所以车辆无法进行超车，当左边一辆高速车接近右侧一辆低速车时，为了避免车祸，高速车会把速度降下来和低速车紧贴着行驶。这样的车辆就会属于同一个同速度同位置的小组。请问最终会形成多少个小组？
一步一步来，先填空
再举例子，找规律……
当然，我不会告诉你们规律的哈，说也不会说给你们听的哈
代码来啦
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100010;
ll n,x,s[N];
int main(){freopen("jam1.in","r",stdin);freopen("jam1.out","w",stdout);cin>>n;for(ll i=0;i<n;i++){cin>>x>>s[i];}ll ans=1;ll speed=s[n-1];for(ll i=n-2;i>=0;i--){if(s[i]<=speed) ans++;speed=min(s[i],speed);}cout<<ans<<endl;return 0;
}希望这些对大家有用，三连必回
这篇关于Peter算法小课堂—贪心算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
