P1090 合并果子

NOI

 2019/05/30 

一维数组做法

本题是一个简单的 Huffman树。Huffman编码在 UTF-8 & Unicode 中都有它思想的体现，即出现频率高的编码长度短，出现频率低的编码长度长，用以缩短整体编码长度

这里我也运用了前面 P1309 的思想：因为每次需要重新排序的时候只有一个数据需要被插入整个数列当中,所以并不需要假定数据无序的 quick sort，反而是线性的排序更快

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int n,berry[10005];long long ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>berry[i];

    sort(berry+1,berry+1+n);

	for(int i=1;i<=n-1;i++){
        berry[i+1]=berry[i]+berry[i+1];///计算每个果堆的重量
        ans+=berry[i+1];///答案是每次搬的果堆的重量之和
        if(berry[i+1]>berry[i+2]){///解决前两个数之和大于第三/四个数的情况（比如有 1 1 1 1）最优解为4而不是7
            for(int j=i+1;j<=n-1;j++){
                if(berry[j]>berry[j+1]) swap(berry[j],berry[j+1]);///线性排序
            }
        }
    }

    cout<<ans;

    return 0;
}

归并做法

据说是离散化算法就是先把原本的从小到大排序排好。然后用两个队列，一个是存储原本的，另一个是存储合成的（由于原本的是从小到大所有新开的也是从小到大）。然后在两个队列的头取最小的，执行两次然后把这两个合并加入第二个队列中。然后由于输入： (1≤ai≤20000)(1≤ai≤20000)(1≤ai≤20000) ，所以用桶排序就可以 O(n)O(n)O(n) 时间复杂度

要义是储存原本果堆的a1是按顺序排列的，所以存储两两合成的新果堆的a2也是按顺序排列的。取这两个果堆序列中最小的两个果堆，必定获得这一步能获得的最小的果堆。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int k,x,num,n1,n2,a1[30001],a2[30001],t[20001],w,sum;
int main()
{
    scanf("%d",&num);
    memset(a1,127/3,sizeof(a1));
    memset(a2,127/3,sizeof(a2));
    for (int i=1;i<=num;i++)
    {
        scanf("%d",&x);
        t[x]++;//桶
    }
    for (int i=1;i<=20000;i++)
    {
        while (t[i])//通排序
        {
            t[i]--;
            a1[++n1]=i;
        }
    }
    int i=1,j=1;
    k=1;
    while (k<num)
    {
        if (a1[i]<a2[j])//取最小值
        {
            w=a1[i];
            i++;
        }
        else
        {
            w=a2[j];
            j++;
        }
        if (a1[i]<a2[j])//取第二次
        {
            w+=a1[i];
            i++;
        }
        else
        {
            w+=a2[j];
            j++;
        }
        a2[++n2]=w;//加入第二个队列
        k++;//计算合并次数
        sum+=w;//计算价值
    }
    printf("%d",sum);
}

二叉（小根）堆

s 代表 son, p 代表 parent, size 代表整个二叉堆中存储的数据数量

完美二叉树, 完全二叉树和完满二叉树的区分

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
int n,heap[maxn],size=0;
void up(int p) //二叉小根堆向上调整（子节点小于父节点就调整）
{
  while(p>1)
  {
    if(heap[p]<heap[p/2])
    {
      swap(heap[p],heap[p/2]);
      p/=2;
    }
    else break;
  }
}
void insert(int val) //二叉堆插入，新元素放在堆底，向上调整
{
  heap[++size]=val;
  up(size);
}
void down(int p) //二叉小根堆向下调整
{
  int s=p*2;
  while(s<=size)
  { //下面这句话是从左右儿子中选一个更小的做交换
    if(s<size&&heap[s+1]<heap[s]) s++; 
    if(heap[s]<heap[p])
    {
      swap(heap[s],heap[p]);
      p=s; s=p*2;
    }
    else break;
  }
}
void extract() //二叉堆删除堆顶
{
  heap[1]=heap[size--]; //将堆底移至堆顶，向下调整
  down(1);
}
int gettop() //返回堆顶的值
{
  return heap[1];
}
int main()
{
  cin>>n;
  for(int i=1; i<=n; i++)
  {
    int a; cin>>a;
    insert(a); //建立二叉堆
  }
  long long ans=0; //其实这里不会越界，但好像原题数据是3万
  while(size>=2) //如果还可合并
  {
    int top1=gettop(); //取出堆顶（堆中最小值）后删除堆顶
    extract();
    int top2=gettop(); //同上
    extract();
    ans+=(top1+top2);
    insert(top1+top2); //将两数之和加入二叉堆，重复运算
  }
  cout<<ans<<endl; //输出答案
  return 0;
}

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/P1090%20%E5%90%88%E5%B9%B6%E6%9E%9C%E5%AD%90/

Publish date：May 30th 2019, 12:00:00 am

Update date：June 27th 2019, 8:32:00 pm

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

Next Post

P2678 跳石头
Previous Post

P1309 瑞士轮

CATALOG

1. 一维数组做法
2. 归并做法
3. 二叉（小根）堆