python实现pat 1033. To Fill or Not to Fill (25)

╰半夏微凉° 2022-06-04 06:36 98阅读 0赞

### [题目传送门][Link 1] ###

"""
    整理后的算法
    #1.将加油站按距离排序
    #2.在覆盖范围内，按优先级寻找下一个站点：比该站点价格小的最近站点；终点（或者记终点价格为0）和前者合并；比该站点价格大但范围内最小的站点
    #3.寻找不到下一站点，则输出最远距离
    #4.到达终点，输出价格
    以下代码写得比较粗糙，还有错误，暂时就懒得改了。
    
    ### 解答
    """
    from functools import cmp_to_key
    line0=[float(x) for x in input().split(" ")]
    cmax,D,dpg,N=line0
    N=int(N)
    d=cmax*dpg #满油行驶距离
    gs=[] #记录加油站，价格，距离
    for i in range(N):
        line=[float(x) for x in input().split(" ")]
        gs.append(line)
    gs.sort(key=cmp_to_key(lambda x,y:x[1]-y[1]))
    dis_c=0 #当前的位置
    pri_c=gs[0][0] #当前价格
    i_c=0  #价格对应的加油站
    dis_m=d  #最大的行驶范围
    oil_c=0
    i = 1
    i_m=0
    flag_next=False
    sum_d=0
    #循环条件写得很乱
    while(i<N):
        flag = True
        j=i
        for pri,dis in gs[i:]:
            if dis <= dis_m:
                if flag:
                    pri_m=pri
                    flag=False
                if pri<=pri_m:
                    flag_next=True
                    pri_m=pri
                    i_m=j
                if pri_m<pri_c:
                    break
            else:
                break
            j += 1
        if flag_next and i_m<N:
            #如果行程范围内的加油站价格最小值大于当前加油站的价格，那就充满油到最便宜的加油站
            if pri_c<=pri_m:
                sum_d+=pri_c*(cmax-oil_c)
                oil_c=cmax-(gs[i_m][1]-dis_c)/dpg
            #如果行程范围内的加油站价格最小值小于当前加油站的价格，那就充足够的油使其正好能到达最便宜的加油站
            if pri_c>pri_m:
                sum_d+=pri_c*((gs[i_m][1]-dis_c)/dpg-oil_c)
                oil_c=0
            i=i_m
            i+=1
            dis_c=gs[i_m][1]
            dis_m=dis_c+d
            pri_c=pri_m
        else:
            dis_c=dis_c+d
            print("The maximum travel distance = %.2f"%dis_c)
            break
    if D-dis_c<=d:
        sum_d+=pri_c*((D-dis_c)/dpg-oil_c)
        print("%.2f"%sum_d)
    else:
        dis_c = dis_c + d
        print("The maximum travel distance = %.2f" % dis_c)

### 结果 ###

一边写一边考虑算法，解答的比较乱，还存在错误。暂时没空修改了。  
![这里写图片描述][SouthEast]

[Link 1]: https://www.patest.cn/contests/pat-a-practise/1033
[SouthEast]: /images/20220604/40bbbe85b95645b2a2faa0592b1ccb9d.png