当前位置：首页 > news >正文

[Python] 位置相关的贪心算法-刷题+思路讲解版

news 来源：原创 2025/8/25 11:33:10

位置贪心-题目目录

例题1 - 香蕉商人
- 编程实现
- 输入描述
- 输出描述
- 思路
- AC代码
例题2 - 分糖果
- 编程实现
- 输入描述
- 输入样例
- 输出样例
- 思路
- AC代码
例题4 - 分糖果II
- 编程实现
- 输入描述
- 输出描述
- 输入样例
- 思路
- AC代码
例题3 - 分糖果III
- 编程实现
- 输入描述
- 输出描述
- 输入样例
- 输出样例
- 思路
- AC代码
例题4 - 上课
- 编程实现
- 输入描述
- 输入样例1
- 输出样例1
- 样例说明1
- 输入样例2
- 输出样例2
- 样例说明2
- 思路
- AC代码

注: 所有题目名字为作者自己起的, 不与洛谷等网站的题有关联.

例题1 - 香蕉商人

编程实现

小A是一名香蕉商人，目前已经知道某段时间香蕉的价格表，由于精力有限，皮皮在香蕉没有卖完的情况下不会进货香蕉，小A人缘很好，一旦出售香蕉，一定会全部卖完。当天卖出，当天买入也可以。现在请你帮小A计算他在这段时间能获得的最大利润。
例如：
连续6天的香蕉价格表：7 1 5 3 4 6
那么小A可以在第2天进价香蕉，在第3天售出香蕉，获得利润为4；
然后在第4天进价香蕉，在第6天售出香蕉，获得利润为3；
故而最大利润为3+4=7。

输入描述

第一行一个数据n，表示天数。
第二行n个数据，表示香蕉在这n天之中的价格。

输出描述

一个数据，表示能够获得的最大利润。
样例输入

6
7 1 5 3 4 6

样例输出

思路

我们只需要拿当前价格和后面一天的价格做比较, 如果当前价格>明天价格, 就计算差值并累加.这样就能算出最大利润.

AC代码

n = int(input())
ls = [int(i) for i in input().split()] 
tot = 0
# 遍历比较每一天与后一天的价格, 注意是从0到n - 1而不是0~n(0~n会越界)
for i in range(0, n - 1):if ls[i] < ls[i + 1]:# 加上每次获得的利润tot += ls[i + 1] - ls[i]
print(tot)

这个就是一个简单的位置相关的贪心, 只要找到上面这个思路就很容易写出代码.

例题2 - 分糖果

编程实现

老师准备了许多糖果，来分给班里的n个孩子，糖果的总数一定是n的倍数，于是老师先大致的把糖果分为了编号为1到n的n堆糖果，但现在每一堆的糖果数量是随机分配的，因此需要公平公正的你来帮助老师完成糖果堆的划分，划分规则为只能把当前堆的糖果移动到相邻的糖果堆，并且每次只能移动一颗，请问最少需要移动多少次才能让每一堆的糖果数量一致？
例如：
n = 4，4堆糖果数量分别为：

9 9 12 10

那么至少需要移动3次糖果
第3堆糖果移动2颗给第2堆，变为：

9 11 10 10

第2堆糖果移动1颗给第1堆，变为：

10 10 10 10

一共移动了三颗糖果，这是最少的移动次数，为3。

输入描述

第一行输入1个正整数n，表示糖果的堆数；
第二行输入n个正整数，空格隔开，表示n堆糖果初始的数量。
输出描述
输出最少需要的移动次数。

输入样例

4
9 9 12 10

输出样例

思路

从第一个人开始遍历, 多的往右给, 少的从右借, 更新计数器, 获得答案.

AC代码

n = int(input())
ls = [int(i) for i in input().split()]
# 所有糖果平均值
avg = sum(ls) // n
cnt = 0
# 分糖果过程
for i in range(n - 1):# 当前糖果堆偏差值x = ls[i] - avg# 计算移动次数cnt += abs(x)# 其后糖果堆变化ls[i + 1] += x
print(cnt)

位置贪心其实代码比较简单, 思路想好就yyds了.

例题4 - 分糖果II

编程实现

老师准备了许多糖果，来分给班里的n个孩子，于是老师先大致的把糖果分为了编号为1到n的n堆糖果，但现在每一堆的糖果数量是随机分配的，老师有一份糖果分配名单，需要你来帮助老师将糖果堆变为为名单上的样子，划分规则为只能把当前堆的糖果移动到相邻的糖果堆，并且每次只能移动一颗，请问最少需要移动多少次才能符合老师的分配名单？
例如：
n = 5，5堆糖果数量分别为：
1 2 3 4 5
老师的分配名单为：
3 1 2 5 4
那么至少需要移动4次糖果：
第2堆糖果移动1颗给第1堆，变为：
2 1 3 4 5
第3堆糖果移动1颗给第2堆，变为：
2 2 2 4 5
第2堆糖果移动1颗给第1堆，变为：
3 1 2 4 5
第5堆糖果移动1颗给第4堆，变为：
3 1 2 5 4
一共移动了4颗糖果，这是最少的移动次数，为4。

输入描述

第一行输入1个正整数n，表示糖果的堆数；
第二行输入n个正整数，空格隔开，表示n堆糖果初始的数量。
第三行输入n个正整数，空格隔开，表示老师的分配名单。

输出描述

输出一行一个数字，表示最少需要的移动次数。

输入样例

5
1 2 3 4 5
3 1 2 5 4

输出样例

思路

其实和上一道题差不多, 只是把abs换成了名单中对应的值而已.

AC代码

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
cnt = 0
# 分糖果过程
for i in range(n - 1):# 当前糖果堆偏差值x = a[i] - b[i]# 计算移动次数cnt += abs(x)# 其后糖果堆变化a[i + 1] += x
print(cnt)

例题3 - 分糖果III

编程实现

老师准备了许多糖果，来分给班里的n个孩子，n个孩子占成一排领取糖果，老师决定让编程积分高的孩子分到更多的糖果，具体划分规则如下：
每个孩子至少分到1颗糖果，并且相邻的孩子，编程积分高的获得的糖果更多。
请问最少需要多少糖果进行发放。

例如：
n = 5，5个孩子的编程积分为：
80 72 89 90 70
那么获得的糖果可为：
2 1 2 3 1
最少需要9颗糖果进行发放。

输入描述

第一行输入1个正整数n，表示孩子的人数；
第二行输入n个正整数，空格隔开，表示每个孩子的编程积分。

输出描述

输出一行一个数字，表示最少需要的糖果数量。

输入样例

5
80 72 89 90 70

输出样例

思路

从左到右遍历, 如果右分>左分, 右糖+1
从右到左遍历, 如果左分<右分且不满足左糖>右糖, 右糖+1

AC代码

n = int(input())
ls = [int(i) for i in input().split()]
# 初始化糖果数，每个孩子至少1颗
nums = [1] * n		# 写成nums = [1 for i in range(n)]也可以for i in range(n - 1):if ls[i] < ls[i + 1]:nums[i + 1] = nums[i] + 1for i in range(n - 1, 0, -1):if ls[i - 1] > ls[i] and nums[i - 1] <= nums[i]:nums[i - 1] = nums[i] + 1 print(sum(nums))

例题4 - 上课

编程实现

皮皮计划有n堂课需要学习，现在给了每堂课的上课和下课时间，由于部分课程存在时间冲突，请你帮皮皮舍掉最少的课程数以至于他的剩余课程不会有时间冲突（上一节下课时间 ≤ 下一节上课时间）。

输入描述

第一行，一个整数n，表示有n节课。
接下来n行，每行2个数据a和b，分别表示该课上课时间和下课时间。
输出描述
一个数据，表示舍掉的课程数量。

输入样例1

输出样例1

样例说明1

只需要将第4节课舍弃，就可保证剩下课程时间连贯。

输入样例2

输出样例2

样例说明2

只需要将重复时间段（1、2或1、3或2、3）的两节课舍弃，就可保证剩下课程时间连贯。

思路

这是一个超级经典的贪心, 重点!!!, 遇到这种问题我们需要按照课程结束时间排序(从小到大)，然后选择不冲突的课程!!!

AC代码

n = int(input())
ls = [[int(i) for i in input().split()] for i in range(n)]
# 按下课时间进行排序
ls = sorted(ls, key=lambda x: x[1])
cnt = 0
# 初始化下课时间为第一个课程的下课时间
end = ls[0][1]
for i in range(1, n):# 如果上课时间小于或等于当前下课时间，舍弃if ls[i][0] < end:cnt += 1# 否则可以上课，更新新的下课时间else:end = ls[i][1]
print(cnt)]

位置贪心-题目目录

例题1 - 香蕉商人

编程实现

输入描述

输出描述

思路

AC代码

例题2 - 分糖果

编程实现

输入描述

输入样例

输出样例

思路

AC代码

例题4 - 分糖果II

编程实现

输入描述

输出描述

输入样例

思路

AC代码

例题3 - 分糖果III

编程实现

输入描述

输出描述

输入样例

输出样例

思路

AC代码

例题4 - 上课

编程实现

输入描述

输入样例1

输出样例1

样例说明1

输入样例2

输出样例2

样例说明2

思路

AC代码

相关文章：