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

題目大意

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

分析

其實(shí)就是每次選兩個(gè)最小的數(shù)相加再放回?cái)?shù)列中。

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

那么，我們的隊(duì)列出廠（當(dāng)當(dāng)當(dāng)當(dāng)）

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;}
隊(duì)列
其實(shí)上面的代碼用到了優(yōu)先隊(duì)列
隊(duì)列
先進(jìn)先出（First In First Out,FIFO）表。STL中為queue。
queue可以在頭部彈出、尾部壓入。
queue<data>a
定義一個(gè)data形的隊(duì)列
queue<data>a(b)
隊(duì)列a為隊(duì)列b的副本
a.push(x)
在隊(duì)列尾部壓入x
a.pop()
彈出隊(duì)列頂部的元素
a.top()
訪問隊(duì)首元素
其他懶得寫
這些就夠了
優(yōu)先隊(duì)列
優(yōu)先隊(duì)列與隊(duì)列的區(qū)別就是優(yōu)先隊(duì)列隊(duì)首元素是最大的。
普通的優(yōu)先隊(duì)列為大根堆，若要轉(zhuǎn)化成小根堆只需元素取相反數(shù)即可。
priority_queue<data>a
定義一個(gè)data形的隊(duì)列
priority_queue<data>a(b)
隊(duì)列a為隊(duì)列b的副本
a.push(x)
在隊(duì)列尾部壓入x
a.pop()
彈出隊(duì)列頂部的元素
a.top()
訪問隊(duì)首元素
其他也懶得寫
這些也就夠了