/*
老板给员工发工资,分成n份,每切一刀收取所划分原长度的价格,用花费最少的方案
权重最优问题,哈夫曼树
*/
#也可以考虑小顶堆来求最小的两个数据
#include<stdio.h>
void ArrSortInsert(int arr[], int n)
{
int temp;
for (int i = 1; i <= n - 1; i++)
{
temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
int CostMin(int arr[], int n)
{
int sum = 0, add;
while (n > 1)
{
ArrSortInsert(arr, n);
add = arr[0] + arr[1];
sum += add;
arr[0] = add;
for (int i = 1; i < n - 1; i++)
arr[i] = arr[i + 1];
n--;
}
return sum;
}
int main()
{
int arr[] = { 8,5,6,7,3,2,1 };
int n = 7;
printf("%d
", CostMin(arr, n));
getchar();
}