小工具知识网

当前位置: 首页 > 行业知识 > 【蓝桥杯备赛】Day12:贪心算法

行业知识

【蓝桥杯备赛】Day12:贪心算法

2026-11-21 12:05:52 来源:互联网转载

题目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)

知识点

  1. 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

    知识点

    1. 考验思维能力,利用贪心思维,先把最大的电池放进去,消耗完,这样总能把若干个电池变为三个电池的问题,335、355,分析得 结果都是总数/2,像3355、333555等这种都是总数/2,符合结论
    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))

    知识点

    1. 本题贪心的思想在于追求最终的时间最少,那么计算不同选手的时间(那些提前出发的不计算)
    2. 贪心一些题目,其实思路非常简单,实在不会,就从样例与题目数据找到关联
    3. 注意单位问题,比如骑车 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)

    知识点

    1. sys库是标准库,sys.stdin是python标准输入通道,file.readline()每次调用返回新的一行,而file.readlines()返回一个列表,列表中每一个元素对应 一行内容,最后用ctrl+D结束输入(Windows)
    2. 本题本质考察数学思维,想要使得包裹数量最少,就是使得每一个包裹剩余的空间最少,接下来开始分析一个6*6 的包裹的各种情况,分别用a,b,c,d,e,f代表产品数量
    3. 6*6:f个,需要f个包裹
    4. 5*5:需要e个包裹,剩余11个1*1空间
    5. 4*4:需要d个包裹,剩余5个2*2 或 20个1*1空间(优先给2*2)
    6. 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
      1. 因为这种分类并没有什么规律,所以建立一个列表,利用索引,进行情况一 一对应
      2. 22:之前的空间优先分给它,形成d5+list[c%4] (list=[0,5,3,1]),然后与b比较,看够不够用,若不够用,每9个会增加一个新的包裹量
      3. 11:利用已经确定的包裹数量,(因为11非常万能,只要有空间,就能放),减去其余各个的空间,最后与a比较,若不够用,每36个会增加一个新的包裹量

    上一篇:快速上手HTML代码,轻松构建网页标题!

    下一篇:房管局备案章表怎么填