我的天啊，這三題code都一樣

題目大意

給你一些數(shù)，每次可以選取兩個相加成為一個，新數(shù)即為得分。所有數(shù)加成一個后，求最小得分。

分析

其實就是每次選兩個最小的數(shù)相加再放回數(shù)列中。

如果用sort效率極低（每次都要sort，時間復(fù)雜度為O(n^2*logn））

那么，我們的隊列出廠（當當當當）

Code

#include<iostream>#include<cstdio>#include<queue>using namespace std;long long int i,m,n,j,k;PRiority_queue<long long int>a;int main(){	cin>>n;	for(i=1;i<=n;i++){		scanf("%d",&k);		a.push(-k);	}	for(i=1;i<n;i++){		int x,y;		x=-a.top();		a.pop();		y=-a.top();		a.pop();		m+=x+y;		a.push(-x-y);	}	cout<<m;	return 0;}
隊列
其實上面的代碼用到了優(yōu)先隊列
隊列
先進先出（First In First Out,FIFO）表。STL中為queue。
queue可以在頭部彈出、尾部壓入。
queue<data>a
定義一個data形的隊列
queue<data>a(b)
隊列a為隊列b的副本
a.push(x)
在隊列尾部壓入x
a.pop()
彈出隊列頂部的元素
a.top()
訪問隊首元素
其他懶得寫
這些就夠了
優(yōu)先隊列
優(yōu)先隊列與隊列的區(qū)別就是優(yōu)先隊列隊首元素是最大的。
普通的優(yōu)先隊列為大根堆，若要轉(zhuǎn)化成小根堆只需元素取相反數(shù)即可。
priority_queue<data>a
定義一個data形的隊列
priority_queue<data>a(b)
隊列a為隊列b的副本
a.push(x)
在隊列尾部壓入x
a.pop()
彈出隊列頂部的元素
a.top()
訪問隊首元素
其他也懶得寫
這些也就夠了