13. 郭老师爱合并果子

• 一. 描述
• • • • 输入格式
      • 输出
• 二. 分析
• 三. 解决
• • 1.踩坑
  • 2.数组
  • • • 解决方法
      • 几个小坑
  • 3.堆（小根堆）
  • • • （1） 复习
      • （2）代码
  • 4.c++ STL 优先队列
  • • • 代码如下

郭老师家有个果园，每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆，但由于体力有限，郭老师在每次合并的时候只能将两堆果子合并到一起。假设有n堆果子，那么经过n-1次合并即可完成任务，且消耗的总体力等于每次合并所消耗的体力之和。

因为郭老师还需要保留体力将果子运回家，所以在合并果子过程中要尽可能地节省体力。假定每个果子重量均为1​，并且已知果子的种类数和每种果子的数目，你的任务是设计出合理的合并方案，使郭老师耗费的体力最少。

例如有​3种果子，数目依次为1,2,9​。合并方案如下：

将1, 2 ​ 合并，得到新堆数目为3​，耗费体力为3​。

将新堆与第三堆合并，又得到新堆，数目为​12，耗费的体力为12​。

总共消耗体力为3+12=15 ​，可以证明​15为最小的体力耗费值。

输入包括两行，第一行是一个整数 [ n ( 1 ≤ n ≤ 100000 ) ] [n(1 le n le 100000)] [n(1≤n≤100000)]​，表示果子的种类数。第二行包含n个整数，用空格分隔，第 ​i 个整数 [ a i ( 1 ≤ a i ≤ 1000000000 ) ] [{a_i}(1 le {a_i} le 1000000000)] [ai​(1≤ai​≤1000000000)] ​是第 i ​ 种果子的数目。

输出包括一行，这一行只包含一个整数，即最小的体力耗费值。

• 消耗的体力是每次消耗的体力叠加，那么每次都要选择最少的两个来搬运，这样一定是最省力的做法
• 如果只有一堆的话,那么是不需要合并的,消耗的体力是0, 而不是这一堆果子的重量

• 利用快速排序算法对输入的序列进行排序,然后去最小的两个来相加,sum的值叠加

#include
#include

void quicksort(int a[],int begin,int end){
    if(begintemp){
                j--;
            }
            a[i]=a[j];
            while(i100000){
        return 0;
    }

    a = (int*)malloc(sizeof(int)*n);
    if(!a){
        return 0;
    }
    for(i=0;i 
乐学疯狂报错, 因为每次都要取最小的两个堆来合并, 忽视了sum合并后的堆可能就不是最小的堆了, 也就是说sum合并以后要放到里面在进行一次排序,然后再选择最小的两个来合并
 
2.数组 
把输入的果子重量存在一个数组里面, 然后每次通过for循环找到最小的和第二小的数,进行相加,相加完的新数再放到原数组里面
 不断的重复这个过程,直到所有的都被合并
 
#include
#include
#define MAXN 1000000001;
long int sum=0;
long int n;
long int start=0;

void GetMinSum(long int a[]){
    long int i;    //遍历
    long int index1=start,index2=start;  //相应下标
    long int min=a[start],small=MAXN;  //最小值,  次小值

    for(i=start+1;ia[i]){
            min = a[i];
            index1 = i;
        }
    }
    for(i=start;i100000){
        return 0;
    }
	a = (long int*)malloc(sizeof(long int)*n);
    if(!a)  //申请内存是否成功
        return 0;
    
    for (long int i = 0; i < n; i++){
        scanf("%ld", &a[i]);
        if(a[i]<1||a[i]>1000000000)  //判断输入数据是否正确
            return 0;        
    }		
    //只有一堆的情况
	if (n == 1)
	{
		printf("0n");
		return 0;
	}	
	//重复n-1次
    whileflag = n-1;
	while (whileflag)
	{
		GetMinSum(a);
		whileflag--;
	}
    
	printf("%ldn", sum);
 
	return 0;
}
 
这个方法是没有问题的, 不过还是无法AC, 因为最后三个例子超过了时间限制
 看了看程序中可能的几个可以减少的操作
 
if(a[i]<1||a[i]>1000000000)  //判断输入数据是否正确
            return 0; 
 
结果还是不行,估计是每一次都要遍历整个数组来找到这两个数, 真正的问题出在这里
 
解决方法 
思路:先对数组进行一次排序(升序),然后取出前两个数, 操作完以后存到一个备用数组中，之后的操作每次只要从原数组和备用数组中各拿出两个数，然后在这四个数中选择两个，然后结果继续存到备用数组中，这样大大减少了遍历的元素数量，这个方法我没有编出来，不过是可行的，有人AC了
 
几个小坑 
MAXN的值要设得足够大，刚开始我以为999999已经很大了，结果测试用例里面还就有边界1000000000的数，导致我卡了一会儿
声明变量时使用long int ，在输出printf的时候一定要记得也要使用long int，顾前不顾后也会出错
 
3.堆（小根堆） 
最近刚好在学二叉树的相关知识，刚好通过编程来复习巩固一下，这个题使用小根堆就能AC，每次排序的时候只会操作一个分支，并不会对所有的数据都来排序，减少了时间复杂度
 
（1） 复习 
-堆结构是一种数组对象，它可以被视为一棵完全二叉树，树中的每个节点存放的值与数组中元素是对应的
 
（2）代码 
//小根堆是一种特殊形式的完全二叉树,可以使用数组来存储
//注意其中很巧妙的下标2倍关系
//从1开始存,0号元素不使用,可以很好的利用上下标的2倍关系
#include
#include

long int *heap;  
long int heapSize=0;  //堆元素个数
long int sum=0;

void swap(long int *a,long int *b){
	long int temp;
	temp = *a;
	*a=*b;
	*b=temp;
}

//存入新数,从末尾存,然后排序
void put(long int num){
	long now,next;
	heap[++heapSize]=num;  //初始值是0,使用前自增
	now=heapSize;
	while(now>1){   
		next=now>>1;  //位运算,相当于/2,速度更快
		if(heap[now]>=heap[next])   //符合结构,直接退出,其他地方都是有序的
			break;
		swap(&heap[now],&heap[next]);  //没有直接退出,说明需要交换
		now = next;
	}
}

//弹出表头,只能从头操作,然后把最后一个数放到根的位置上,排序处理
long int pop(){
	long int now=1,next,res=heap[1];
	heap[1]=heap[heapSize];
	heapSize--;

	while(now*2<=heapSize){  //保证有左分支
		next = now*2;
		if(next1){
		temp = pop()+pop();  //这两个pop()可不一样哦
		sum +=temp;
		put(temp);   //存进去,会自动处理成小根堆
		n--;
	}
	printf("%ldn",sum);

	return 0;
}
 
swap函数是c++里面才有的，这里需要自己写一下
 -这是我第一次写的swap函数，我把指针传进去进行操作以达到更改原数组元素的值，但是函数内部是在尝试交换a和b的值，这里a和b的值是地址，而不是数据，地址是固定的
 
void swap(long int *a,long int *b){
	long int temp;
	temp = a;
	a=b;
	b=temp;
}
 
对比正确的交换函数
 
void swap(long int *a,long int *b){
	long int temp;
	temp = *a;
	*a=*b;
	*b=temp;
}
 
应该更改的是这个地址对应的值
 
4.c++ STL 优先队列 
这个题限定了只能使用c语言，如果是c++的话可以更简单快捷
知识回顾

 优先队列priority_queue
 用法1： priority_queueq; //建立大根堆，每次可以取出元素的最大值
 用法2：priority_queue, greater>q; //建立小根堆，每次取出的元素为最小值

 基本操作：
 empty（） 队列为空返回真
 pop（） 出队，删除队首（之后会自动调整为堆）
 push（） 入队，（会自动调整）
 size（） 返回拥有的元素个数
 top（） 返回队首元素（一般为最大值或者最小值）
 
代码如下 
//priority_queue得到的是一个大根堆,使用负数来达到小根堆的效果

#include
#include
#include
#include
#include

using namespace std;

priority_queueq;

int main()
{
	int n,i,x,t,sum=0;
    //freopen("file in.txt","r",stdin);
	cin>>n;
	for(i=1;i<=n;++i)
	{
		cin>>x;
		q.push(-x);
	}
	while(--n)
	{
		t=0;
		t-=q.top(); //得到一个正数
        q.pop();    //删除头
		t-=q.top();
        q.pop();
		sum+=t;
		q.push(-t);  
	}
	cout<