压缩数据

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode{
 int _val;
 TreeNode* _left{ nullptr }, *_right{ nullptr };
 TreeNode(int val) :_val(val){}
};

struct cmp{
 bool operator ()(TreeNode* t1, TreeNode* t2)
 {
  return t1->_val > t2->_val;
 }
};

int main()
{
 //freopen("in.txt", "r", stdin);
 int n,val;
 while (cin >> n && n)
 {
  priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
  for (int i = 0; i < n; ++i)
  {
   cin >> val;
   pq.emplace(new TreeNode(val));
  }
  while (pq.size() > 1)
  {
   auto p1 = pq.top();
   pq.pop();
   auto p2 = pq.top();
   pq.pop();
   auto p = new TreeNode(p1->_val + p2->_val);
   p->_left = p1;
   p->_right = p2;
   pq.emplace(p);
  }

  int res = 0;
  int bits = 0;
  vector<TreeNode*> cur{ pq.top() };
  while (!cur.empty())
  {
   vector<TreeNode*> next;
   for (auto& node : cur)
   {
    if (!node->_left && !node->_right) res += bits * node->_val;
    if (node->_left) next.emplace_back(node->_left);
    if (node->_right) next.emplace_back(node->_right);
   }
   swap(cur, next);
   ++bits;
  }
  cout << res << endl;
 }
 return 0;
}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    priority_queue<int,vector<int>,greater<int> >que;
    int n=0;
    while(cin>>n){
        int sum=0;
        int temp;
        while(n--){
            cin>>temp;
            que.push(temp);
        }
        while(true){
            temp=que.top();
            que.pop();
            temp+=que.top();
            que.pop();
            sum+=temp;
            if(que.empty())
                break;
            que.push(temp);
        }
        cout<<sum<<endl;
    }
} 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int  n;
    while(cin>>n)
    {
        vector<int> v(n);
        for(auto &x:v)
            cin>>x;
        make_heap(v.begin(),v.end(),greater<int>());
        int res=0;
        vector<int> num(n);
        while(v.size()>=2)
        {

            pop_heap(v.begin(),v.end(),greater<int>());
            int tmp=v.back();
            v.pop_back();
            pop_heap(v.begin(),v.end(),greater<int>());
            tmp += v.back();
            v.pop_back();
            res+=tmp;
            v.push_back(tmp);
            push_heap(v.begin(),v.end(),greater<int>());
        }
        cout<<res<<endl;
    }
    return 0;
}

// write your code here
//博客里有分享思路https://blog.csdn.net/m0_37924505/article/details/79757590
import java.util.*;
public class Main {  public static void main(String[] args)
 {  Scanner sc = new Scanner(System.in);  while(sc.hasNext()) {  int num = sc.nextInt();  int[] figure = new int[num];  for (int i = 0; i  figure[i] = sc.nextInt();  }  LinkedList arr = new LinkedList();  for (int i = 0; i  arr.add(new Node(figure[i]));  }  //数字从小到大排序  Comparator comparator = new Comparator() {  @Override  public int compare(Node o1, Node o2) {  return o1.val-o2.val;  }  };    ArrayList myMaps = new ArrayList();  Node root = getHuffmanDataSpace(arr, comparator);  int dep =0;//节点深度  //遍历树  gainHuffmancode(root,myMaps,dep);  int getres = getres(myMaps);  System.out.println(getres);  }  }    //构造树，返回根节点  public static Node getHuffmanDataSpace(LinkedList arr,Comparator comparator) {  while(arr.size()!=1) {  Collections.sort(arr,comparator);  Node n1 = arr.removeFirst();  Node n2 = arr.removeFirst();  Node n3 = new Node(n1.val+n2.val);  n3.left=n1.val n3.right=n1.val>n2.val?n1:n2;  arr.add(n3);  }  return arr.get(0);  }  /**   *   * @param root 二叉树   * @param hashMap  （字符数量，代表字母数量哈夫码空间大小）   * @param figure 储存字符数量的数组   */  public static void gainHuffmancode(Node root, ArrayList myMaps, int dep) {  if(root.left==null&&root.right==null) {  myMaps.add(new MyMap(root.val, dep));  return;  }  if(root.left!=null) {  dep++;  gainHuffmancode(root.left, myMaps,  dep);  dep--;  }  if(root.right!=null) {  dep++;  gainHuffmancode(root.right, myMaps,  dep);  dep--;  }    }    public static int getres(ArrayList myMaps) {  int totalspace = 0;  //遍历myMaps  for (MyMap myMap : myMaps) {  totalspace +=myMap.key*myMap.value;  }  return totalspace;  }    //构造树节点  static class Node{  int val;  Node left;  Node right;  public Node(int val) {  this.val = val;  }  }    static class MyMap{  int key;  int value;  public MyMap(int key,int value) {  this.key=key;  this.value=value;  }  }   }

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int[] arr = new int[n];
			for (int i = 0; i < arr.length; i ++ ) {
				arr[i] = sc.nextInt();
			}
			System.out.println(Hoffman(arr));
		}
	}
	public static int Hoffman(int[] arr) {
		PriorityQueue<Node> queue = new PriorityQueue<>();
		for (int i = 0; i < arr.length; i ++ ) {
			Node node = new Node(arr[i], null, null);
			queue.add(node);
		}
		Node root = null;
		while (queue.size() > 1) {
			Node left = queue.poll();
			Node right = queue.poll();
			root = new Node(left.weight + right.weight, left, right);
			queue.add(root);
		}
		return getLength(root, 0);
	}
	public static int getLength(Node node, int level) {
		if(node.left == null || node.right == null) return node.weight * level;
		return getLength(node.left, level + 1) + getLength(node.right, level + 1);
	}
	static class Node implements Comparable<Node> {
		int weight;
		Node left;
		Node right;
		public Node(int weight, Node left, Node right) {
			this.weight = weight;
			this.left = left;
			this.right = right;
		}
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
	}
}

#include<stdio.h>
#define N 100
int main()
{

    int n;
    int top,size;
    int pool[N][2];
    while(scanf("%d",&top)!=EOF){

        for(int i=0;i<top;i++)
        {
            scanf("%d",&pool[i][0]);
            pool[i][1] = -1;//标记是否使用过 -1表示未筛选用过
        }
        n = top;
        size = top;
        while(n!=1){//pool里面不只一个数据

            int m1,m2;
            int s = 0;
            for(int i = 0; i < top; i++)
            {
                if(pool[i][1]==-1)
                {
                    s = i;
                    break;
                }

            }
            m1 = s;//未选择数据中 找最小的
            for(int i = s; i < top; i++)
            {
                if(pool[i][0] < pool[m1][0] && pool[i][1]==-1)
                {
                    m1 = i;
                }
            }
            pool[m1][1] = top;//指向父节点


            for(int i = 0; i < top; i++)
            {
                if(pool[i][1]==-1 && i!=m1)
                {
                    s = i;
                    break;
                }

            }
            m2 = s;//未选择数据中 找次小的
            for(int i = s; i < top; i++)
            {
                if(pool[i][0] < pool[m2][0] && pool[i][1]==-1 && i!= m1)
                {
                    m2 = i;
                }
            }
            pool[m2][1] = top;
            pool[top][1] = -1;
            pool[top++][0] = pool[m1][0]+pool[m2][0];
            /*for(int i=0;i<top;i++)
            {
                if(pool[i][1]==-1)
                    printf("%d ",pool[i][0]);
            }
            printf("\n");*/

            n--;//可用数据减1
        }

        for(int i=0;i<size;i++)
        {
            int step = 0;
            int cur = i;
            while(pool[cur][1]!=-1)
            {
                step++;
                cur = pool[cur][1];
            }
            pool[i][1] = step;//确定数据的访问步数(亦 树节点的高度)
        }
        int sum = 0;
        for(int i=0;i<size;i++)
            sum += pool[i][0]*pool[i][1];
         printf("%d\n",sum);
    }
    return 0;
}