好厉害的算法...队列..但是只用一个就行了..我真苯...当年怎么会用Heap呢..

By YJ狗狗

heap是堆拉，傻瓜！！！！！！！！！

问一个白痴点的问题 heap 是什么意思啊

用哈夫曼树的算法.....

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 119ms

├ 测试数据 06：答案正确... 619ms

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

再来一个heap的...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

差距咋这大呢...

用堆排

不用时间就过了

贪心算法--选取质量最小的两堆将它们合并

每次寻找最小值时需要O(n)的时间,总得时间复杂度是O(n^2)!!

优化的时候就想起了小根堆!(用WinnerTree偶也不管).所以寻找是就降到了O(log2n).

总得复杂度:

时间:O(nlog2n)

空间:O(n)

O(n)的算法如下：

先把原来的果子排序（当然用桶排，因为每堆重量在1..20000内）

开两个队列

第一个存原来的（可以在排序的过程中直接存进去）

第二个存之后的（每次合并的结果）

显然 第一个队列由于经过了排序 肯定是递增的

然后，每次从两个队列的队首取出比较小的那个数 取两次

加起来塞到第二个队列的末尾

第二个队列由于是每次取最小的两个求和再放进去 也肯定是递增的

直到两个队列加起来只有1个元素为止 那个就是答案

显然排序是常数时间，而两个队列的长度差不多 因此总体是O(n)的算法

---|---|---|---|---|---|---|---|---|---|---|---|-

To YJ狗狗: 只用1个队列可以吗? 请说明做法

To hbxfwz: 测试数据中确实做到了每堆

#include <cstdio>
#include <queue>
#define int long long
using namespace std;
queue <int> q1;
queue <int> q2;
int to[100005];
void read(int &x){
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;}
signed main() {
int n;read(n);
for (int i = 1; i <= n; ++i) {
int a;read(a);to[a]++;}
for (int i = 1; i <= 100000; ++i) {
while(to[i]) {to[i] --;q1.push(i);}}
int ans=0;
for (int i=1;i<n;++i){
int x,y;
if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){
x=q1.front();q1.pop();}
else{x=q2.front();q2.pop();}
if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){
y=q1.front();q1.pop();}
else{y=q2.front();q2.pop();}
ans+=x+y;q2.push(x + y);}
printf("%lld" ,ans);
return 0;}

就是一个huffman编码的问题，最小的次数最多，最大的次数最少。
这题用优先队列可以做到nlogn，因为队列找出最小和次小只要logn
当然可以用线性查找的方式，最后就是n平方了，不过也可以AC。

这题和POJ3253几乎一模一样，注意POJ那边用long long。

麻烦的用了优先队列，不过长度可以忍受了。

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> que;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0,x;i<n;++i)
    {
        scanf("%d",&x);
        que.push(-x);
    }
    int ans=0;
    for(int i=1,tmp;i<n;++i)
    {
        tmp=que.top();
        ans-=que.top();
        que.pop();
        tmp+=que.top();
        ans-=que.top();
        que.pop();
        que.push(tmp);
    }
    cout<<ans<<endl;
    return 0;
}

优先队列比较快
cpp
#include<bits/stdc++.h>
using namespace std;
struct cmp{
bool operator()(int a,int b){
return a>b;
}
};
priority_queue<int,vector<int >,cmp> a;
int main(){
int n,sum=0,num;
cin>>n;
for(int i=0;i<n;i++){
cin>>num;
a.push(num);
}
if(a.size()==1){
cout<<a.top()<<endl;
return 0;
}
while(a.size()>1){
int temp1,temp2;
temp1 = a.top();
a.pop();
temp2 = a.top();
a.pop();
//cout<<temp1<<"　"<<temp2<<endl;
sum+=(temp1+temp2);
a.push(temp1+temp2);
}
cout<<sum<<endl;
return 0;
}


二叉堆
const maxn=30000;
var heap:array[1..maxn] of longint;
ans,n,len,a,b,i,tmp:longint;

procedure put(x:longint);
var fa,son,tmp:longint;
begin
len:=len+1;
heap[len]:=x;
son:=len;
while (son<>1)and(heap[son div 2]>heap[son]) do
begin
tmp:=heap[son div 2];
heap[son div 2]:=heap[son];
heap[son]:=tmp;
son:=son div 2;
end;
end;
function get:longint;
var fa,son,tmp:longint;
stop:boolean;
begin
get:=heap[1];
heap[1]:=heap[len];
len:=len-1;
fa:=1; stop:=false;
while ((fa*2<=len)or(fa*2+1<=len))and(not stop) do
begin
if (fa*2+1>len)or(heap[fa*2]<heap[fa*2+1])
then son:=fa*2
else son:=fa*2+1;
if heap[fa]>heap[son]
then begin
tmp:=heap[fa];
heap[fa]:=heap[son];
heap[son]:=tmp;
fa:=son;
end
else stop:=true;
end;
end;
begin
len:=0;
read(n);
for i:=1 to n do
begin
read(tmp);
put(tmp);
end;
ans:=0;
for i:=1 to n-1 do
begin
a:=get;
b:=get;
ans:=ans+a+b;
put(a+b);
end;
writeln(ans);
end.

呵呵呵，一遍过了，水题，pascal堆 都没什么其他操作了。。。。。
var h:array[0..30000]of longint;
j,n,i,len,x,a,b:longint;
ans:int64;
procedure put(x:longint);
var fa,son,t:longint;
begin
len:=len+1; h[len]:=x; son:=len;
while (son<>1)and(h[son div 2]>h[son]) do
begin
t:=h[son div 2];h[son div 2]:=h[son]; h[son]:=t;
son:=son div 2;
end;
end;
function get:longint;
var fa,s,t:longint;
begin
get:=h[1]; h[1]:=h[len]; len:=len-1; fa:=1;
while fa*2<=len do
begin
if (fa*2+1>len)or(h[fa*2+1]>h[fa*2]) then s:=fa*2
else s:=fa*2+1;
if h[fa]>h[s] then
begin
t:=h[fa];
h[fa]:=h[s];
h[s]:=t;
fa:=s;
end
else break;
end;
end;
begin
readln(n); len:=0;
for i:=1 to n do
begin
read(x); put(x);
end;
for i:=1 to n-1 do
begin a:=get; b:=get; ans:=ans+a+b;put(a+b); end;
write(ans);
end.

优先队列
单调队列 都可以用