Peter算法小课堂—贪心算法

2023-12-14 06:11:16

课前思考:贪心是什么?贪心如何“贪”?

课前小视频:什么是贪心算法 - 知乎 (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;
}

希望这些对大家有用,三连必回

文章来源:https://blog.csdn.net/zhang040818/article/details/134862745
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。