Peter算法小课堂—贪心算法

这篇具有很好参考价值的文章主要介绍了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号,如此进行直到娃娃们排好了顺序。

请求出将娃娃们排好顺序所需要的最小操作次数。

 举例子,找规律

Peter算法小课堂—贪心算法,算法,贪心算法

经过几小时的找规律,我们会发现……

Peter算法小课堂—贪心算法,算法,贪心算法 

所以说呢…… 

如果排列最后有连续最多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辆车正在从左向右行驶。每辆车的当前位置各不相同,各自的速度也可能不同。因为只有一条车道,所以车辆无法进行超车,当左边一辆高速车接近右侧一辆低速车时,为了避免车祸,高速车会把速度降下来和低速车紧贴着行驶。这样的车辆就会属于同一个同速度同位置的小组。请问最终会形成多少个小组?

一步一步来,先填空

Peter算法小课堂—贪心算法,算法,贪心算法 

再举例子,找规律……

当然,我不会告诉你们规律的哈,说也不会说给你们听的哈

代码来啦

#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;
}

希望这些对大家有用,三连必回文章来源地址https://www.toymoban.com/news/detail-753369.html

到了这里,关于Peter算法小课堂—贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Peter算法小课堂—线性dp

    今天,你读完这篇文章,普及组的动态规划已经可以秒了。 求两个数列的最长公共子序列(Longest Common Subsequence,LCS)的长度。 数列 X 和 Y 的最长公共子序列 Z,是指 Z 既是 X 的子序列,又是 Y 的子序列,而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。 f[i][j]表示

    2024年04月23日
    浏览(33)
  • Peter算法小课堂—自定义容器

    这个算法复杂度为O(nm),显然有更快的算法  但是,这样写有个很危险的错误,如下 运行出来是这样的,  原因很简单,因为set的功能是排序、去重,然而结构体排序要加上“.\\\",所以会报错 改后代码, 那么,回到原题,代码该怎么写呢? 当然这个代码也有高级版,但要升

    2024年02月04日
    浏览(37)
  • Peter算法小课堂—拓扑排序与最小生成树

    讲拓扑排序前,我们要先了解什么是DAG树。所谓DAG树,就是指“有向无环图”。请判断下列图是否是DAG图 第一幅图,它不是DAG图,因为它形成了一个环。第二幅图,它也不是DAG图,因为它没有方向。第三幅图才叫真正的DAG图(DAG图不一定联通)。 那什么叫DAG图的拓扑排序呢

    2024年01月21日
    浏览(46)
  • 算法小课堂(五)贪心算法

    贪心算法是一种常见的算法思想,用于解决优化问题。其基本思想是在每一步选择中都采取当前状态下最优的选择,从而希望能够获得全局最优解。 具体来说,贪心算法通常分为以下步骤: 定义问题的最优解,通常需要将问题转化为求最大值或最小值; 选择一个局部最优解

    2024年02月02日
    浏览(41)
  • 【算法小课堂】二分查找算法

    当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率是非常低下,所以在实际中这种查找的方法是被摒弃的。

    2024年02月08日
    浏览(37)
  • 算法小课堂(十)随机化算法

    目录 一、概述 1.1概念 1.2分类 二、数值随机化算法 2.1随机数 2.2用随机投点法计算Π值  2.3随机投点法计算定积分  三、舍伍德(Sherwood)型随机化算法 3.1随机洗牌算法 3.2随机快速排序:随机选择枢点的快速排序算法 3.3找出这n个元素中第k小的元素。 四、拉斯维加斯(LasVe

    2024年02月03日
    浏览(36)
  • 【算法小课堂】深入理解前缀和算法

    前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。 我们通过一个例子来理解前缀和算法的优势: www.nowcoder.com 我们可以通过暴力的解法去解决这个问题,但是这

    2024年02月08日
    浏览(36)
  • 【算法小课堂】动态规划

    动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是叙述概念,讲解原理,让人觉得晦涩难懂,即使一

    2024年01月25日
    浏览(40)
  • 算法小课堂(四)动态规划

    目录 一、概况 二、背包 2.0闫式dp分析法 2.1 0-1背包 朴素解法 滚动数组 2.2 完全背包 朴素解法 优化降维 滚动数组 2.3完全背包和0-1背包的区别与联系 2.4多重背包问题 朴素解法 二进制枚举优化 贪心算法 单调队列优化 2.5分组背包问题 朴素算法 优化降维 二进制枚举优化 三、线

    2023年04月27日
    浏览(54)
  • 【算法小课堂】滑动窗口

    滑动窗口本质是双指针算法的一种演变 本质上就是同向双指针,窗口的范围就是[left,right) 滑动窗口大致可以分为两类 窗口大小不变的 窗口大小变化的 滑动窗口遇到一些验证重复性的问题的时候可以用哈希表来优化 三步走: 窗口的形成初期 进窗口 开始遍历数组,right一直

    2024年02月07日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包