位置贪心-题目目录
注: 所有题目名字为作者自己起的, 不与洛谷等网站的题有关联.
例题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
样例输出
7
思路
我们只需要拿当前价格和后面一天的价格做比较, 如果当前价格>明天价格, 就计算差值并累加.这样就能算出最大利润.
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
输出样例
3
思路
从第一个人开始遍历, 多的往右给, 少的从右借, 更新计数器, 获得答案.
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
输出样例
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
输出样例
9
思路
从左到右遍历, 如果右分>左分, 右糖+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] + 1
for 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
4
1 2
2 3
3 4
1 3
输出样例1
1
样例说明1
只需要将第4节课舍弃，就可保证剩下课程时间连贯。
输入样例2
3
1 2
1 2
1 2
输出样例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)]