拼多多满减优惠 AC代码 python

思路就是从价值最高的优惠券开始遍历尝试，价值相同的优惠券则先尝试需要满足的金额小的，然后用在比满减所需金额大的商品中最便宜的那个上，就ok

from sys import stdin as f
[n,m] = [int(i) for i in f.readline().split()]
price = sorted([int(i) for i in f.readline().split()],reverse=True)

dc = {}
for i in range(m):
    [man,jian] = [int(i) for i in f.readline().split()]
    if jian in dc:
        dc[jian]+=[man]
    else:
        dc[jian]=[man]
        
for k,v in dc.items():
    dc[k] = sorted(v)


def used():
#    dc = deepcopy(dcc)
    num = 0
    dc_value = sorted(dc,reverse = True)
    while price and dc_value:
        
        dc_max = dc_value[0]
        
        if price[0]<dc[dc_max][0]:
            dc.pop(dc_max)
            dc_value.pop(0)            
            continue
#        print(dc)
        mv = dc[dc_max].pop(0)
            
        
        index = 0
        while index<len(price):
            if (index+1)<len(price) and price[index+1]>=mv:
                index+=1
            else:
                break
            
        num+= dc_max
#        print(num)
        price.pop(index)
        
        if not dc[dc_max]:
            dc.pop(dc_max)
            dc_value.pop(0)
            
    return num

all_m = sum(price)
print(all_m - used())