PAT划水记

贪心,模拟

Pat数据比较水，py都能过

Pat 1033 To fill or not to fill
贪心，水题

stations = list()
minPrice = 1e5
maxArrived = 0
cmax=0
d=0
davg=0
n=0
def find_next_station(currTotalPrice,curr,gasLength,max_len):
    global stations,cmax,d,davg,n,minPrice,maxArrived
    sindex=list()
    currLen = stations[curr]['distance']
    currIndex = curr
    cheapPrice =1e5
    cheapIndex=0
    flag = False
    for i in range(curr+1,len(stations)):
        if(flag==False and stations[i]['distance']-currLen<=max_len ):
            sindex.append(i)
            if(stations[i]['price']<stations[curr]['price']):
                cheapPrice = stations[i]['price']
                cheapIndex = i
                flag=True
    if(len(sindex)>0):
        if(cheapPrice<stations[curr]['price']):
            pushGasLen = stations[cheapIndex]['distance'] - stations[curr]['distance']-gasLength
            currTotalPrice+=stations[curr]['price'] * pushGasLen*1.0/(davg*1.0)
            gasLength+=pushGasLen
        else:
            if(stations[curr]['distance']+max_len>=d):
                pushGasLen = d - stations[curr]['distance'] -gasLength;
                currTotalPrice += stations[curr]['price'] * pushGasLen*1.0/(davg*1.0);
                if(currTotalPrice < minPrice):
                    minPrice=currTotalPrice
                maxArrived = d
                return
            else:
                pushGasLen = max_len - gasLength
                currTotalPrice+=stations[curr]['price'] * pushGasLen*1.0/(1.0*davg)
                gasLength = max_len
        if(cheapIndex!=0):
            curr = cheapIndex
        else:
            curr = sindex[len(sindex)-1];
        gasLength -= stations[curr]['distance']-stations[currIndex]['distance']
        find_next_station(currTotalPrice,curr,gasLength,max_len)
    else:
        if(stations[curr]['distance']+max_len>=d):
            lastDistance = d-stations[curr]['distance']
            currTotalPrice =currTotalPrice+ (lastDistance*1.0/davg)*stations[curr]['price']
            if(currTotalPrice<minPrice):
                minPrice = currTotalPrice
            maxArrived = d
        else:
            distance = stations[curr]['distance']+max_len
            if(distance>maxArrived):
                 maxArrived = distance;
        return
def main():
    global stations,cmax,d,davg,n,minPrice,maxArrived
    s=input().strip().split()
    cmax=float(s[0])
    d=float(s[1])
    davg=float(s[2])
    n=int(s[3])
    MAX_LEN=cmax*davg
    noway = True
    for i in range(n):
        s=input().strip().split()
        ss={'price':float(s[0]),'distance':float(s[1])}
        stations.append(ss)
        if(ss['distance']==0):
            noway=False
    if(noway):
        print("The maximum travel distance = %.2lf"%maxArrived)
        return
    stations = sorted(stations,key=lambda x:x['distance'])
    find_next_station(0,0,0,MAX_LEN)
    if(maxArrived<d):
        print("The maximum travel distance = %.2lf"%maxArrived)
    else:
        print("%.2lf"%minPrice)
    return
main()

Pat1007 Maximum Subsequence Sum 最大子序列和

n=int(input())
arr=map(lambda x:int(x),input().split(' '))
maxSum,tmpSum = -1,0
ms,mt = -1,-1
ts,tt = -1,-1
for x in arr:
    if ts==-1:
        start=x
    else:
        start=ts
    if tmpSum+x<0:
        tmpSum=0
        ts,tt=-1,-1
    elif tmpSum+x>maxSum:
        tmpSum+=x
        maxSum=tmpSum
        ms=ts=start
        mt=tt=x
    else:
        tmpSum+=x
        ts=start
        tt=x
if ms==-1:
    first_f=True
    f,l=0,0
    for x in arr:
        if first_f:
            f=x
            first_f=False
        l=x
    print("0 %d %d"%(f,l))
else:
    print("%d %d %d"%(maxSum,ms,mt))

Pat 1008 Elevator 模拟，水题

from functools import *
first=True
n=0
f,tt=0,0
for x in input().split():
    if first:
        n=int(x)
        first=False
    else:
        y=int(x)
        if f<y:
            tt+=(y-f)*6
            f=y            
        else:
            tt+=(f-y)*4
            f=y
print(tt+n*5)