我這是個優(yōu)惠券的模塊
優(yōu)惠券有3種:指定商品優(yōu)惠券;供應(yīng)商優(yōu)惠券;全場通用優(yōu)惠券;
每個訂單只能使用一張優(yōu)惠券
使用優(yōu)先規(guī)則
1,金額最大并且符合條件優(yōu)先使用
2,金額一樣的話優(yōu)先按 指定的商品 - 指定供應(yīng)商 - 全場通用 從高至低優(yōu)先級使用
現(xiàn)在假設(shè) 我在購物車同時結(jié)算2個不同供應(yīng)商的商品(不同供應(yīng)商會分訂單)A 和 B ,現(xiàn)在我有2張符合條件的優(yōu)惠券,一張指定A商品的優(yōu)惠券 20元,一張全場通用券30元,按照之前的規(guī)則,會自動選擇A商品使用全場優(yōu)惠券,B就不能使用優(yōu)惠券了。
但是如果A用20的優(yōu)惠券,B也能用通用優(yōu)惠券。我卡在這里了- -
求大佬指點迷津!!我是個小渣渣,我渴望進步!
說一下算法思路吧, 以下python偽代碼
訂單數(shù)組 A (A0, A1...An) n個, 優(yōu)惠券數(shù)組 B (B0,B1...Bm), 其中B0 (金額、類型),類型:A0~An或c0~ck指定供應(yīng)商或M全場通用。
#用一個hashmap存下來類型數(shù)組, 并用排序
d = {}
for i in B:
if i[1] in d:
bisect.insort(d[i[1]], i[0]) #二分法有序插入金額
else:
d[i[1]] = [i[0]] # 金額數(shù)組
#時間復(fù)雜度O(mlogk) (k<=m)
#懶得用A的優(yōu)惠券數(shù)組了,A也用hashmap,第一遍給所有的商品分配最高的商品優(yōu)惠券
a = {} #key商品名,value優(yōu)惠券價格
for i in A:
if i in d:
a[i] = d[i][0] #最高優(yōu)惠券
d[i].pop(0)
else:
a[i] = 0 #沒有商品優(yōu)惠券0
#時間復(fù)雜度O(n)
#第二遍分組從低到高給所有的商品分配最高的供應(yīng)商優(yōu)惠券
#供應(yīng)商字典C (C0,...Ck) 其中C0的value 是(A0,..At)
for c in C:
r = sorted([(a[i], i) for i in C[c]], lambda x: x[0]) # 根據(jù)價格排序,同組價格低的排最前面
if not r:
continue #沒有這個組不用計算啦
rindex = 0
while d[c]: #還有供應(yīng)商優(yōu)惠券
if d[c][0] <= r[rindex][0]:
break #比商品優(yōu)惠券低,不要算啦
a[r[rindex][1]] = d[c][0] #低的商品優(yōu)惠券不要啦,給高的供應(yīng)商優(yōu)惠券
rindex += 1
d[c].pop(0)
#時間復(fù)雜度O(k.tlogt)
#最后給全場優(yōu)惠券啦
r = sorted([(a[i], i) for i in a], lambda x: x[0])# 根據(jù)價格排序,價格低的排最前面
rindex = 0
while d['M']: # 有全場通用券
if d['M'][0] <= r[rindex][0]:
break #全場通用券太低啦,不要算啦
a[r[rindex][1]] = d['M'][0] #低的優(yōu)惠券不要啦,給高的全場通用券
rindex += 1
d['M'].pop(0)
print(a) #最后的結(jié)果啦
#時間復(fù)雜度O(nlogn)
#總得時間復(fù)雜度取決于t、n、m的大小啦
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團,成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達內(nèi)教育集團成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機構(gòu),是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負責(zé)iOS教學(xué)及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術(shù)顧問,美國Dachieve 系統(tǒng)架構(gòu)師,美國AngelEngineers Inc. 系統(tǒng)架構(gòu)師。