哈夫曼树

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            PriorityQueue<Integer> q = new PriorityQueue<Integer>();
            for(int i=0;i<n;i++)
                q.add(in.nextInt());
            int ans = 0;
            while(q.size()>1){
                int first = q.poll();
                int sec = q.poll();
                ans += (first + sec);
                q.add(first+sec);
            }
            System.out.println(ans);
        }
    }
}

#include<iostream>
#include<limits.h>
using namespace std;

typedef struct HuffmanNode{
    long int weight;
    int parent;
    int lchild;
    int rchild;
}HuffmanNode,*HuffmanTree;

void select(int& s1,int& s2,HuffmanTree T, int n);

int main()
{
    int n;
    HuffmanTree Tree;
    while(cin>>n)
        {
        int m=2*n-1;
     Tree=(HuffmanTree)malloc(sizeof(HuffmanNode)*(m+1));
  int i;
  for(i=1;i<=n;i++)
  {
   int weight;
         cin>>weight;
   Tree[i].weight=weight;
   Tree[i].parent=0;
   Tree[i].lchild=0;
   Tree[i].rchild=0;
  } 
  for(;i<=m;i++)
  {
   Tree[i].weight=0;
   Tree[i].lchild=0;
   Tree[i].rchild=0;
   Tree[i].parent=0;
  }
  for(i=n+1;i<=m;i++)
  {
   int s1,s2;
   select(s1,s2,Tree,i-1);
   Tree[i].lchild=s1;
   Tree[i].rchild=s2;
   Tree[s1].parent=i;
   Tree[s2].parent=i;
   Tree[i].weight=Tree[s1].weight+Tree[s2].weight;
  }
  long int sum=0;
  for(i=1;i<=n;i++)
  {
   int p,f,j=0;
   for(p=i,f=Tree[p].parent;f!=0;p=f,f=Tree[p].parent)
   {
    j++;
   }
   sum=sum+(Tree[i].weight*j);
  }
  cout<<sum<<endl;
     free(Tree);
    }
    
   return 0;  
}

void select(int& s1,int& s2,HuffmanTree T,int n)
{
 int i;
 long int min=LONG_MAX,secMin=LONG_MAX;
 for(i=1;i<=n;i++)
 {
  if(T[i].parent==0)
  {
   if(T[i].weight<=min)
   {
    s2=s1;
    secMin=min;
    s1=i;
    min=T[i].weight;    
   }
   else if(T[i].weight<=secMin)   
   {
    s2=i;
    secMin=T[i].weight;
   }
  }
 }
}
 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int n, sum, temp;
    vector<int> s;
    while(cin >> n)
    {
        sum = 0;
        for(int i = 0; i!= n; ++i)
        {
            cin >> temp;
            s.push_back(temp);
        }
        int bg = 0, ed = n;
        while(ed-bg != 1)
        {
            sort(&s[bg], &s[ed]);
            temp = s[bg++] + s[bg++];
            sum += temp;
            s.push_back(temp);
            ed++;
        }
        cout << sum << endl;
        s.clear();
    }
}

#include<stdio.h>
int a[1000],n;
int min(int a[])//找最小的数
{
    int min=a[0],minindex=0,i;
    for(i=1;i<n;i++)
        if(a[i]<min)
        {
            min=a[i];
            minindex=i;
        }
    a[minindex]=a[n-1];
    n--;//把最后一个数放在最小位置,然后长度减一
    return min;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int ans=0,min1,min2;
    while(n>1)//剩下的大于俩结点
    {
        min1=min(a);//两个结点
        min2=min(a);
        ans+=min1+min2;//结果
        a[n]=min1+min2;//新增的结点
        n++;
    }
    printf("%d\n",ans);
}

#include <iostream>
#include <queue>
using namespace std;

struct cmp {
	bool operator() (const int & a, const int & b) {
		return a > b;
	}
};

int main() {
	//freopen("t.txt", "r", stdin);

	int n;
	while(cin>>n) {
		priority_queue<int, vector<int>, cmp> pq;
		for(int i = 0; i<n; i++) {
			int t;
			cin>>t;
			pq.push(t);
		}
		int res = 0;
		while(pq.size() > 1) {
			int a = pq.top(); pq.pop();
			int b = pq.top(); pq.pop();
			int c = a + b;
			res += c;
			pq.push(c);
		}
		cout<<res<<endl; 
	}
}

#include<iostream>
#include<queue>
using namespace std;
int main(){
    int n,temp,a,b;
    int weight;
    priority_queue<int,vector<int>,greater<int>> minheap;
    while(cin>>n)
    {
        weight = 0;
        for(int i= 0;i < n;i++)
        {
            cin>>temp;
            minheap.push(temp);
        }
        while(minheap.size()!= 1)
        {
            a = minheap.top();
            minheap.pop();
            b = minheap.top();
            minheap.pop();
            weight = weight + a +b;
            minheap.push(a+b);
             
        }
        cout<<weight<<endl;
        minheap.pop();
    }    
    return 0;
}

#include<iostream>
 #include<algorithm>
 using namespace std;
 int main() {
     int number[1000];
     int n,result;
     while (cin >> n) {
         result = 0;
         for (int i = 0; i < n; i++)cin >> number[i];
         for (int i = 0; i < n-1; i++) {
             sort(number+i, number + n);
             number[i + 1] = number[i] + number[i + 1];
             result += number[i + 1];
         }
         cout << result << endl;
     }
 }

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,arr[1000];
    while(cin>>n)
    {
            for(int i=0;i<n;++i)
                cin>>arr[i];
            int answer=0,i=0;
            while(i!=n-1)
            {
                sort(arr,arr+n);
                arr[i+1]=arr[i]+arr[i+1];
                answer+=arr[i+1];
                ++i;
            }
            cout<<answer<<endl;
    }
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args)  {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()) {
			int n = scanner.nextInt(), sum = 0;
			int[] nums = new int[n];
			for(int i = 0; i < n; i++) {
				nums[i] = scanner.nextInt();
			}
			for(int i = 0; i < n - 1; i++) {
				Arrays.sort(nums, i, n);
				nums[i + 1] = nums[i] +nums[i + 1];
				nums[i] = 0;
				sum += nums[i + 1];
			}
			System.out.println(sum);
		}
	}
}

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct HuffmanTree{
    int data;
    int weight;
    HuffmanTree *lchild,*rchild;
} HT;
int n;
vector<HT> seq;
bool cmp(HT a,HT b){
    return a.data<b.data;
}
void insert_node(HT* node){
    if(seq.empty()){
        seq.push_back(*node);
        return;
    }
    vector<HT>::iterator it = seq.begin();
    for(it;it != seq.end();it++){
        if(node->data <= it->data){
            seq.insert(it,*node);
            return;
        }
    }
    seq.push_back(*node);
}
HT* buildHT(){
    while(1){
        HT *fnode = (HT*) malloc(sizeof(HT));
        HT *node_l = (HT*) malloc(sizeof(HT));
        HT *node_r = (HT*) malloc(sizeof(HT));
        *node_l = seq[0];
        *node_r = seq[1];
        fnode->data = node_l->data + node_r->data;
        fnode->lchild = node_l;
        fnode->rchild = node_r;
        seq.erase(seq.begin());
        seq.erase(seq.begin());
        insert_node(fnode);
        if(seq.size() == 1){
            return fnode;
        }
    }
}
void cal_weight(int &ans,HT* node,int level){
    if(node == NULL) return;
    if(node->lchild == NULL && node->rchild == NULL){
        ans = ans + node->data * level;
        return;
    }
    cal_weight(ans,node->lchild,level+1);
    cal_weight(ans,node->rchild,level+1);
}
int main(){
    int ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        HT *node = (HT*) malloc(sizeof(HT));
        scanf("%d",&node->data);
        node->lchild = NULL;
        node->rchild = NULL;
        seq.push_back(*node);
    }
    sort(seq.begin(),seq.end(),cmp);
    HT* root = buildHT();
    cal_weight(ans,root,0);
    printf("%d",ans);
    return 0;
}

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * Created by fhqplzj on 17-2-19 at 下午8:03.
 */
public class Huff {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(n);
            for (int i = 0; i < n; i++) {
                priorityQueue.add(scanner.nextInt());
            }
            int result = 0;
            while (priorityQueue.size() > 1) {
                int a = priorityQueue.poll();
                int b = priorityQueue.poll();
                result += a + b;
                priorityQueue.add(a + b);
            }
            System.out.println(result);
        }
    }
}

#include <cstdio> 
#include <iostream>
#include <queue>

using namespace std;

// 求哈夫曼树的带权路径和 
int main() {
	priority_queue<int> pqueue;// 存入相反数（模拟出一个小根堆） 
	int n;
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++) {
			int leaf;
			scanf("%d", &leaf);
			pqueue.push(-leaf);// 模拟小根堆 
		}
		
		int res = 0;// 存储带权路径和的中间结果
		while (pqueue.size() > 1) {
			// 取出最小的两个元素 
			int leaf1 = pqueue.top();
			pqueue.pop();
			int leaf2 = pqueue.top();
			pqueue.pop();
			
			// 计算带权路径和
			res = res + leaf1 + leaf2;
			// 把构成的新子树插入回原来的集合 K中 
			pqueue.push(leaf1 + leaf2);
		}
		printf("%d\n", -res); 
	}
	return 0;
}

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    int n,ans,i;
    priority_queue<int, vector<int>, greater<int>> tmp;
    cin>>n;
    for(i=0;i<n;++i)
    {
        cin>>ans;
        tmp.push(ans);
    }
    int sum=0;
    while(tmp.size()>1)
    {
        int min1,min2;
        min1=tmp.top();
        tmp.pop();
        min2=tmp.top();
        tmp.pop();
        sum+=min1+min2;
        tmp.push(min1+min2);
    }
    cout<<sum<<endl;
    return 0;
}

#include<iostream>
#include<queue>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        priority_queue<int,vector<int>,greater<>> q;
        while(n--){
            int x;
            cin>>x;
            q.push(x);
        }
        int ans = 0;
        while(q.size()>1){
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            ans += a + b;
            q.push(a+b);
        }
        cout<<ans<<endl;
    }
    return 0;
}