可以移动的石子合并

11079 可以移动的石子合并
时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
题型: 编程题语言: 无限制
描述
有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，现要将石子合并成一堆，规定每次可选择至少2堆最多k堆移出然后合并，合并的分值为新堆的石子数。
现在求解将这n堆石子合并成一堆的最低得分和最高得分。
输入格式
两行。第一行n和k，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100，2<=k<=n。
输出格式
仅一行，为石子合并的最低得分和最高得分，中间空格相连。
输入样例
7 3
45 13 12 16 9 5 22
输出样例
199 593
Hint
此题贪心算法求解.
给这题标记标签"dp"方法是同学所为,并非老师标注.动规不是不可以,但有更好更快的贪心解法的.
另外此题老师放上的测试数据有误，现已更正（4月29日更正的），请大家重新提交，并请大家原谅！
贪心的方法如下：
（1）保证每次选两堆最多的，合并直至只剩一堆为止，能获得最大得分；
这个和huffman树构造是相同的，不再详述！
（2）保证每次选k堆最少的，合并直至只剩一堆为止，能获得最小得分。
24
这个是多元huffman树的构造。要注意的是：在合并之前，若n%(k-1)!=1，说明合并到最后一轮时，剩下不是k堆（而是比k堆少），这样算的并不是最小得分，
而必须在合并之前添加若干个为0的虚拟堆，目的为凑成的堆数保证每次都能有k堆合并（包括最后一次）最后合并为1堆。
因此，在合并前作如下处理：
//假设石头每堆个数放于stone[1]~stone[n],且stone[n]之后最多k-1个数组单元为可写;
while (n % (k - 1) != 1)
{
n++;
stone[n]=0;
}

---------------------------------------------------------------

11079可以移动的石子合并（贪心）

#include<stdio.h>

#include<malloc.h>

intsort(int*a,intn)//一定要有返回值

{

inti,j,temp;

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

if(a[i]<a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}

}

return0;

}

intmain()

{

intn,i,j,*a,sum=0,temp=0,m,k,maxSum=0;

scanf("%d",&n);

scanf("%d",&k);

a=(int*)malloc((n+k)*sizeof(int));

for(i=0;i<n;i++)

scanf("%d",&a[i]);

sort(a,n);

temp=a[0];

for(i=1;i<n;i++)

{

temp+=a[i];

maxSum+=temp;

}

while(n%(k-1)!=1)

{

n++;

a[n-1]=0;

}

m=n;

while(m!=1){

temp=0;

sort(a,m);

for(j=1;j<=k;j++)

temp+=a[m-j];

a[m-k]=temp;

sum+=temp;

m=m-k+1;

}

printf("%d",sum);

printf("%d\n",maxSum);

return0;

}