[数据结构与算法]合并果子问题（贪心算法）

题意：有n堆果子，重为ai。 每次合并果子消耗的体力为两堆果子重量之和。求消耗的最小体力。

转换：每次从n个数中取出最小的两个数，累加它们的和。数列中去掉了这两个数，新增了它们的? ? ? ? ? ? ? ? ?和。

思路1：类似于前缀和，对数组进行一次排序，求出每个数与它前一个数的和并存在另一个数组?b? ? ? ? ? ? ??里。循环找出b中的最小值，进行累加，并更改最近的非0相关数据。

? ? ? ? ? ? ?弊端：过于复杂，且没有必要再增一个b进行二级修改。对0的处理过于繁琐且易出错。是? ? ? ? ? ? ? ? ? ? ? ? ? 思考不成熟的表现。应该继续思考再打代码，不然会在错误方向上浪费很多时间。

思路2：对数组进行排序，循环，取 i 和 i+1 位置上的数相加，更新i+1位置上数的值。若 i > i+1

? ? ? ? ? ? ? 则再次排序。

? ? ? ? ? ? ?弊端：时间复杂度过高，过了5个测试点。

int phy(int m, int n, int*a, int size, int k)
{
	k+=a[m] + a[n];
	a[n]+=a[m];
	if(n==size-1) return k;
	if(a[n]>a[n+1]) qsort(a,size,sizeof(a[0]),cmp);
	phy(n,n+1,a,size,k);
    
}

思路3：时间损耗最大的地方是排序。其实可以不排序，只取出最小的两个数即可。

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define N 10005

int n,a[N],phy=0;

int df(int x)  //选择排序
{
	int p = x;
	for(int i=x+1; i<n; i++)
	{
		if(a[i]<a[p]) p=i;
	}
	if(p!=x) {
		int t=a[p];
		a[p]=a[x];
		a[x]=t;
	}
	return a[x];
}

int main(void)
{

  scanf("%d",&n);
  for(int i=0; i<n; i++) scanf("%d",&a[i]);
  for(int i=0; i<n-1; i++)
  {
	phy+=df(i) + df(i+1);
	a[i+1]+=a[i];             
  }
  
  printf("%d",phy);
}