題目

題目分析

1. 對于本題首先確定其數(shù)據(jù)結(jié)構(gòu)為優(yōu)先隊(duì)列，即郵費(fèi)最小的衣服優(yōu)先寄，算法符合貪心算法。
2. 可以直接使用queue庫的PriorityQueue方法實(shí)現(xiàn)優(yōu)先隊(duì)列。
3. 關(guān)于PriorityQueue的使用方法主要有：

import queue
q = queue.Queue()# 隊(duì)列
pq = queue.PriorityQueue()# 優(yōu)先隊(duì)列
>>> q.put(10)#10入隊(duì)
>>> q.qsize()#隊(duì)列大小
1
>>> q.get()#出隊(duì)并返回隊(duì)首元素
10
>>> q.empty()#隊(duì)列是否為空
True

4. 尤其注意使用put()函數(shù)時，第一個參數(shù)priority值越小優(yōu)先級越高，也就是對首總是最小值。
5. 其實(shí)如果使用手寫list的方法使用list的sort()方法也可以實(shí)現(xiàn)升、降序排列。
6. 本題題目簡短卻值得深思，可以把染色過程反過來思考，開始，所有的衣服顏色完全不同，最后染成同一種顏色，顯然每次都寄出郵費(fèi)最便宜的兩種顏色的衣服，將他們?nèi)境赏ㄒ环N顏色，是最省錢的。可以將已經(jīng)染成同一顏色的兩件衣服邏輯上合并為1件衣服，在每個合并步驟中取最小的兩個郵費(fèi)相加，新的郵費(fèi)在后面繼續(xù)累加即可。
7. 整個過程和哈夫曼樹的原理很相似，貪心算法中運(yùn)用較多。

題解

import queue
pq=queue.PriorityQueue()
n=int(input())
a =list(map(int,input().split()))
for i in range(len(a)):pq.put(a[i])
sum=0
while pq.qsize()>1:t=pq.get()+pq.get()sum+=tpq.put(t)
print(sum)