codeforces_734C python的sort()函数 python的bisect

Anton and Making Potions

安东和他的药水

安东做一份药水有2种方法：

1.把做药水的时间X换成Ai，花费Bi 魔法

2.一瞬间做成Ci份药水,花费Di 魔法

问，最少需要多少时间

二分魔法值

n,m,k = list(map(int,input().split()))
x,s = list(map(int,input().split()))
a_time = list(map(int,input().split()))
a_cost = list(map(int,input().split()))
b_num = list(map(int,input().split()))
b_cost = list(map(int,input().split()))

def binary_search(manapoints):
    global  k,b_cost
    l = 0;  r = k-1;  pos = -1
    while (l <= r):
        mid = int((l+r)/2)
        if (b_cost[mid] <= manapoints):
            l = mid+1;  pos = mid;
        else :
            r = mid-1
    return pos
res = n*x
pos = binary_search(s)
if (pos >= 0):  res = min(res,(n-b_num[pos])*x);
for i in range(m):
    if (a_cost[i] > s): continue;
    rest = s-a_cost[i]
    pos = binary_search(rest)
    if (pos >= 0):  res = min(res,(n-b_num[pos])*a_time[i])
    else : res = min(res,n*a_time[i])
print(res)

接下来是Python学习时间

xxx.append(x[i],xx[i])

Python 的二维数组

可以直接sort

xxx.sort() (按照x[i]的大小进行从小到大排序）

为什么会这样呢？

sort()函数原型

xxx.sort(cmp=None, key=None, reverse=False)

　　

reverse ：

False（从小到大） True （从大到小）

key:

xxx.sort(key = lambda x:x[2])按照x[2]大小排序

cmp:

xxx.sort(cmp=g)

def g(x,y):

　　returu x[0]-y[0]

Python的bisect（好像会比正常写二分查找来的快很多）

import bisect

a = [1234,235,64,123]
a.sort(reverse=True)
print(a)
print(bisect.bisect(a,22222))  #其目的在于查找该数值将会插入的位置并返回，而不会插入。

bisect.insort(a,3) #其目的在于查找该数值将会插入的位置并返回，会插入。
print(a)

print(bisect.bisect_left(a,3)) #其目的在于查找该数值将会插入的左边位置并返回，而不会插入。
print(bisect.bisect_right(a,3)) #其目的在于查找该数值将会插入的右边位置并返回，而不会插入。

bisect.insort_left(a,3) #其目的在于查找该数值将会插入的左边位置并返回，会插入。
print(a)
bisect.insort_right(a,3) ##其目的在于查找该数值将会插入的右边位置并返回，会插入。
print(a)