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

【蓝桥杯python研究生组备赛】003 贪心

news 来源：原创 2025/8/21 1:01:38

题目1 股票买卖

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含整数 N，表示数组长度。

第二行包含 N 个不大于 10000 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

1≤N≤105

输入样例1：

6
7 1 5 3 6 4

输出样例1：

输入样例2：

5
1 2 3 4 5

输出样例2：

输入样例3：

5
7 6 4 3 1

输出样例3：

样例解释

样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

python代码

n=int(input())
data=list(map(int,input().split()))ans=0for i in range(n-1):if data[i+1]>data[i]:ans+=data[i+1]-data[i]print(ans)

知识点

主要是在于思路：任何多日间的低买高卖，都可以被简化为每两天之间的交易

题目2 货仓选址

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 N。

第二行 N 个整数 A1∼AN。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤100000,
0≤Ai≤40000

输入样例：

4
6 2 9 1

输出样例：

python代码

n=int(input())data=list(map(int,input().split()))
ans=0
data.sort()
if n%2==0:#n为偶数,选在中间两个数中间place=data[n//2-1]
else:#n为奇数，选在中位数place=data[n//2]#计算总距离
for i in range(n):ans+=abs(data[i]-place)
print(int(ans))

知识点

思路问题，首先是无疑是把货仓建在商店中间
当n为偶数，放在中间的两个中的一个
当n为偶数，放在中间的一个

题目3 糖果传递

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

求使所有人获得均等糖果的最小代价。

输入格式

第一行输入一个正整数 n，表示小朋友的个数。

接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤n≤1000000,
0≤a[i]≤2×10^9,
数据保证一定有解。

输入样例：

输出样例：

python代码

n=int(input())
data=[0]
n1=n
while n1:a=int(input())data.append(a)n1-=1
ave=sum(data)//n
c=[0]*(n+1)for i in range(n):c[i+1]=c[i]+data[i]-ave
# print(c)
ans=0
c=[0]+sorted(c[1:n+1])
# print(c)
for i in range(1,n+1):#下标从1开始ans+=abs(c[i]-c[n//2+1])
print(ans)

知识点

糖果传递

图例中的c1与代码中的c1不是一致的
c1-c4均可正可负
将问题转化为，已知a1,a2,a3,a4,求距离每一个点最小的距离和，而最优解就是中位数

题目4

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 d，当小岛与某雷达的距离不超过 d 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 x 轴，海的一侧在 x 轴上方，陆地一侧在 x 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式

第一行输入两个整数 n 和 d，分别代表小岛数目和雷达检测范围。

接下来 n 行，每行输入两个整数，分别代表小岛的 x，y 轴坐标。

同一行数据之间用空格隔开。

输出格式

输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 −1。

数据范围

1≤n≤1000,
1≤d≤200,
−1000≤x,y≤1000

输入样例：

输出样例：

python代码

n,d=map(int,input().split())data=[list(map(int,input().split())) for _ in range(n)]#先计算覆盖每一个小岛对应的线段
from math import sqrt
data.sort(key=lambda x:x[0])#按照横坐标排序line=[]#存储对应的线段for i in range(n):#如果小岛纵坐标已经大于半径，那么直接输出-1if data[i][1]>d:print(-1)exit()elif data[i][1]==d:a,b=data[i][0],data[i][0]line.append([a,b])else:distance=sqrt(d**2-data[i][1]**2)a=data[i][0]-distanceb=data[i][0]+distanceline.append([a,b])line.sort(key=lambda x:x[1])#按照线段右端点排序
ans=0
last=line[0][1]#上一个雷达点for i in range(1,n):if last>=line[i][0]:ans+=0else:last=line[i][1]ans+=1
print(ans)

知识点

如果以雷达为核心，r为半径的圆，去找覆盖到的小岛，不太容易判断那么就以小岛为圆心，找到能满足要求的线段[a,b]
如果小岛纵坐标已经大于半径，那么直接输出-1
按照右端点对区间进行排序，那么如果下一个需求坐标的左端点在上一个坐标右端点的后面，则需要再放一个雷达，反之，不用放雷达

排序：line.sort(key=lambda x:(x[1],x[0])):先按照line每一个元素的第二个值进行排序，若第二个值相等，按照这个元素的第一个值进行排序。

line=[[1,2],[3,2],[5,2],[-2,4]]
line.sort(key=lambda x:(x[1],x[0]))
print(line)#[[1, 2], [3, 2], [5, 2], [-2, 4]]

更多蓝桥杯笔记：蓝桥杯备赛笔记

题目5 付账问题

几个人一起出去吃饭是常有的事。

但在结帐的时候，常常会出现一些争执。

现在有 n 个人出去吃饭，他们总共消费了 S 元。

其中第 i 个人带了 ai 元。

幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。

这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。

你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。

形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

标准差

输入格式

第一行包含两个整数 n、S；

第二行包含 n 个非负整数 a1, …, an。

输出格式

输出最小的标准差，四舍五入保留 4 位小数。

数据范围

1≤n≤5×105,
0≤ai≤109,
0≤S≤1015。

输入样例1：

5 2333
666 666 666 666 666

输出样例1：

0.0000

输入样例2：

10 30
2 1 4 7 4 8 3 6 4 7

输出样例2：

0.7928

python代码

n,s=map(int,input().split())
data=list(map(int,input().split()))sum1=sum(data)
ave=s/nvar=0
data.sort()
i=0
while i<len(data):mean=s/nif data[i]<=mean:#余额小于均值，只能付出全部var+=(data[i]-ave)**2s-=data[i]n-=1i+=1else:#后面的每一个都大于当前均值var+=(mean-ave)**2*nbreak
var=(var/len(data))**0.5print(f'{var:.4f}')

知识点

贪心原则：局部考虑，当前某一个人距离最终均值最小：

余额少于等于剩余的均值，那么付出所有余额
余额大于剩余的均值，那么之后的所有人都大于该均值，每个人付出该均值

标准化输出：print(f'{var:.4f}'):保留4位小数，浮点型

题目6 乘积最大

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0，我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式

输出一个整数，表示答案。

数据范围

1≤K≤N≤10^5,
−10^5 ≤Ai≤ 10 ^5

输入样例1：

输出样例1：

999100009

输入样例2：

输出样例2：

-999999829

python代码

n,k=map(int,input().split())data=[int(input()) for _ in range(n)]
mod1=10**9+9def mod(x):if x>0:return x%mod1return -(-x%mod1)data.sort()
flag=1#标记是否全是负数
ans=1if k%2!=0:#奇数个,转化为偶数问题ans*=data[-1]n-=1k-=1if data[-1]<0:#全是负数flag=-1l,r=0,n-1 
while k:ll=data[l]*data[l+1]rr=data[r]*data[r-1]if ll*flag>=rr*flag:ans*=llans=mod(ans)l+=2else:ans*=rrans=mod(ans)r-=2k-=2print(ans)

知识点

蓝桥杯笔记：蓝桥杯备赛笔记

主要是要考虑到所有的情况，做到不重复，不遗漏
首先是当n==k,那么就只能所有的数相乘
k为偶数
- 全正：排序后的数据，从右到左即可
- 至少存在一个负数，此时k<n,那么就不选这个负数，剩下选择成对的负数or正数，取绝对值最大的
k为奇数
- 全负：排序后的数据，从左到右即可，结果一定为负
- 至少存在一个正数，此时k<n，那么就选择这个正数，之后从n-1个数中选择k-1个（负数、正数都成对选），此时k-1为偶数，最终结果一定大于等于0

题目7 后缀表达式

给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,···,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N+M+1 个整数 A1,A2,···,AN+M+1。

输出格式

输出一个整数，代表答案。

数据范围

0≤N,M≤105,
−109≤Ai≤109

输入样例：

1 1
1 2 3

输出样例：

思路

蓝桥杯笔记：蓝桥杯备赛笔记

很多贪心题目一下子真的很难想出来，怎么办？找规律
首先保证分类情况没有重复没有遗漏

全是正数
1 2 3 4 5

n=4,m=0:全部相加
n=3,m=1:5+4+3+2-1
n=2,m=2:5+4+3-(1-2)
n=1,m=3:5+4-(1-2-3)
n=0,m=4:2-(1-5-4-3)

全是负数
-5 -4 -3 -2 -1

n=4,m=0:全部相加
n=3,m=1:(-1)-{(-5)+(-4)+(-3)+(-2)}
n=2,m=2:(-1)-{(-5)+(-4)+(-3)}-(-2)
n=1,m=3:(-1)-{(-5)+(-4)}-(-3)-(-2)
n=0,m=4:(-1)-(-5)-(-4)-(-3)-(-2)

有正有负
-5 -4 -3 2 1

n=4,m=0:全部相加
n=3,m=1:(1)-{(-5)+(-4)+(-3)+(2)}
n=2,m=2:(1)-{(-5)+(-4)}-(-3)+(2)
n=1,m=3:(1)-{(-5)}-(-4)-(-3)+2
n=0,m=4:(1)-(-5)-(-4)-(-3)-(-2)

不知道你找到规律没？关键在于减号的数量

减号数量为0，所有元素相加
减号数量不为0，列表中最大元素-最小元素+其余每一个元素的绝对值

import os
import sys
n,m=map(int,input().split())
data=list(map(int,input().split()))
data.sort()
ans=0
if m==0:#一个负号都不存在ans=sum(data)
else:#至少存在一个负号ans=data[-1]-data[0]for i in range(1,len(data)-1):ans+=abs(data[i])
print(ans)

题目8 社区服务

问题描述

为了庆祝妇女节，社区组织了一场“温暖传递”活动。社区中有 $n$ 个服务点排成一列，每个服务点可能有志愿者（用 1 表示）或暂时无人（用 0 表示）。

每个服务点都有居民需要帮助，现在你需要从左往右，为每个无志愿者服务点计算距离最近的有志愿者服务点的距离，若不存在则输出 $- 1$ 。

输入格式

第一行输入一个整数 $n$ （ $\leq n \leq 5000$ ），表示服务点数量。

第二行输入一个长度为 $n$ 的二进制字符串 $S$ ，1 表示当前服务点有志愿者，0 表示当前服务点无志愿者。

数据保证 $S$ 至少包含 $1$ 个 0。

输出格式

输出一行若干个整数，表示每个无志愿者服务点到有志愿者服务点的最近距离，若不存在则输出 $- 1$ 。

样例输入

7 
1010100

样例输出

1 1 1 2

思路

一开始以为全是0，比如000，输出一个“-1”，后来才知道正确答案是“-1 -1 -1”

记录1的下标对于每一个0，遍历1的下标，更新1到0 的距离的最小值如果最终这个最小值找到了，就放进答案列表ans中没有找到这个最小值，即全是0的情况，把-1放进列表

python代码

n=int(input())
data=list(map(int,input()))list_1=[]#存1的下标
for i in range(n):if data[i]==1:list_1.append(i)
ans=[]for i in range(n):ans1=nif data[i]==0:for j in list_1:ans1=min(ans1,abs(j-i))if ans1!=n:ans.append(ans)else:ans.append(-1)print(*ans,sep=' ')

题目1 股票买卖

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

样例解释

python代码

知识点

题目2 货仓选址

输入格式

输出格式

数据范围

输入样例：

输出样例：

python代码

知识点

题目3 糖果传递

输入格式

输出格式

数据范围

输入样例：

输出样例：

python代码

知识点

题目4

输入格式

输出格式

数据范围

输入样例：

输出样例：

python代码

知识点

题目5 付账问题

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

python代码

知识点

题目6 乘积最大

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

python代码

知识点

题目7 后缀表达式

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路

题目8 社区服务

问题描述

输入格式

输出格式

样例输入

样例输出

思路

python代码

相关文章：