行业知识
【蓝桥杯备赛】Day12:贪心算法
题目1:题目 2518: 信息学奥赛一本通T1620-质因数分解
原题���自:NOIP 2012 普及组
()已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。
输入格式
输入只有一行,包含一个正整数 n
()输出格式
输出只有一行,包含一个正整数 p,即较大的那个质数。
样例输入
21
样例输出
7
python代码
import mathn=int(input())j=int(math.sqrt(n))for i in range(2,j+1): if n%i==0: k=n//i breakprint(k)
知识点
- n是两个不同的质数的乘积,只要找到一个数能够被n整除,这个数一定是质数
题目2:题目 3047: Crossing River
几个人过河,每次过两人一人回,速度由慢者决定,问过河所需最短时间。
输入格式
输入t组数据,每组数据第1行输入n,第2行输入n个数,表示每个人过河的时间。
输出格式
输出t行数据,每行1个数,表示每组过河最少时间。
样例输入
1
4
1 2 5 10
样例输出
17
python代码
global times times=[]#记录所有组数据结果def crossingriver(p_list): p_list.sort()#顺序排列 time=0#一组数据 全部过河需要的时间 while True: if len(p_list)128456>>12456
题目4:题目 3044: 电池的寿命
小S新买了一个掌上游戏机,这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏,他买了很多5号电池,这些电池的生产商不同,质量也有差异,因而使用寿命也有所不同,有的能使用5个小时,有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时,那么他只能玩3个小时的游戏,有一个电池剩下的电量无法使用,但是如果他有更多的电池,就可以更加充分地利用它们,比如他有三个电池分别能用3、3、5小时,他可以先使用两节能用3个小时的电池,使用半个小时后再把其中一个换成能使用5个小时的电池,两个半小时后再把剩下的一节电池换成刚才换下的电池(那个电池还能用2.5个小时),这样总共就可以使用5.5个小时,没有一点浪费。
现在已知电池的数量和电池能够使用的时间,请你找一种方案使得使用时间尽可能的长。
输入格式
输入包含多组数据。每组数据包括两行,第一行是一个整数N(2≤N≤1000),表示电池的数目,接下来一行是N个正整数表示电池能使用的时间。
输出格式
对每组数据输出一行,表示电池能使用的时间,保留到小数点后1位。
样例输入
2
3 5
3
3 3 5
样例输出
3.0
5.5
python代码
def bat(list1,n): if max(list1)>sum(list1)-max(list1):#电池有剩余情况 print('%.1f'%(sum(list1)-max(list1))) else:#电池无剩余情况 print('%.1f'%(sum(list1)/2))while 1: try: n=int(input()) list1=list(map(int,input().split())) bat(list1,n) except: break 知识点
- 考验思维能力,利用贪心思维,先把最大的电池放进去,消耗完,这样总能把若干个电池变为三个电池的问题,335、355,分析得 结果都是总数/2,像3355、333555等这种都是总数/2,符合结论
- 3,5 这种情况,电池有剩余,得到结果 是 总和减去最大的
题目5:题目 3043: 骑车上班Ride to Office
起点与终点相隔4500米。现Charley需要从起点骑车到终点。但是,他有个习惯,沿途需要有人陪伴,即以相同的速度,与另外一个人一起骑。而当他遇到以更快的速度骑车的人时,他会以相应的速度跟上这个更快的人。先给定所有与Charley同路的人各自的速度与出发时间,问Charley以这种方式跟人,骑完4500米需要多少时间。得出的结果若是小数,则向上取整。
输入格式
输入若干组数据,每组数据第一行n(1≤n≤10000),n为0,表示输入结束,接着输入n行数据,每行2个数据,表示速度v和出发时间t,如果t=0: s.append(a) t.append(b) for i in range(len(t)): nowtime=math.ceil(t[i]+4500/(s[i]/3.6)) time.append(nowtime) print(min(time))
知识点
- 本题贪心的思想在于追求最终的时间最少,那么计算不同选手的时间(那些提前出发的不计算)
- 贪心一些题目,其实思路非常简单,实在不会,就从样例与题目数据找到关联
- 注意单位问题,比如骑车 30,那么很明显它的单位是m/min,而结果可能是以m/s为单位
题目6:题目 1868: 装包装箱问题
某家工厂制造的某种产品形状都是长方体,并且它们的高度都是 h,长和宽都相等,一共有六个
型号,他们的长宽分别为 11, 22, 33, 44, 55, 66. 这些产品通常使用一个 66h 的长方
体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的
包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由
你来设计
输入格式
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空
格隔开,分别为 11 至 66 这六种产品的数量。输入文件将以 6 个 0 组成的一行结尾。
输出格式
除了输入的最后一行 6 个 0 以外,输入文件里每一行对应着输出文件的一行,每一行输
出一个整数代表对应的订单所需的最小包裹数。
样例输入
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
样例输出
2
1
python代码
import sysdef packaging(p_list): box=0 a,b,c,d,e,f=p_list[0],p_list[1],p_list[2],p_list[3],p_list[4],p_list[5] box=d+e+f+(c+3)//4#3*3-6*6的箱子数量 twolist=[0,5,3,1] need2num=d*5+twolist[c%4]#已经给2*2的个数 if b>need2num: box+=(b-need2num+8)//9#腾出来的数量不够,每多出9个增加一个箱子的数量 else: box+=0 need1num=(box*36-f*36-e*25-d*16-c*9-b*4)#留给1*1的个数 if a>need1num: box+=(b-need2num+35)//36#腾出来的数量不够,每多出9个增加一个箱子的数量 else: box+=0 print(box) while True: line=sys.stdin.readline() if line=='0 0 0 0 0 0': break else: p_list=[] for _ in line.split(): p_list.append(int(_)) packaging(p_list)
知识点
- sys库是标准库,sys.stdin是python标准输入通道,file.readline()每次调用返回新的一行,而file.readlines()返回一个列表,列表中每一个元素对应 一行内容,最后用ctrl+D结束输入(Windows)
- 本题本质考察数学思维,想要使得包裹数量最少,就是使得每一个包裹剩余的空间最少,接下来开始分析一个6*6 的包裹的各种情况,分别用a,b,c,d,e,f代表产品数量
- 6*6:f个,需要f个包裹
- 5*5:需要e个包裹,剩余11个1*1空间
- 4*4:需要d个包裹,剩余5个2*2 或 20个1*1空间(优先给2*2)
- 3*3:最复杂:(拿一个空包裹分析)
- 1个3*3,剩余可放5个2*2+7个1*1
- 2个3*3,剩余可放3个2*2+6个1*1
- 3个3*3,剩余可放1个2*2+5个1*1
- 4个3*3,剩余可放0个2*2+0个1*1
- 因为这种分类并没有什么规律,所以建立一个列表,利用索引,进行情况一 一对应
- 22:之前的空间优先分给它,形成d5+list[c%4] (list=[0,5,3,1]),然后与b比较,看够不够用,若不够用,每9个会增加一个新的包裹量
- 11:利用已经确定的包裹数量,(因为11非常万能,只要有空间,就能放),减去其余各个的空间,最后与a比较,若不够用,每36个会增加一个新的包裹量
下一篇:房管局备案章表怎么填