合并果子加强版
问题描述：有n堆果子，你可以选择最多其中m堆果子合并成一堆，合并的代价是这些果子数量之和，求最后合并成一堆果子的最少总代价。
文件输入：n,m(1<=m<=n<=10000)
以下n行为每堆果子数量(<=10000)
文件输出：一个数为最少总代价；
样例输入：
5 3
3 2 1 4 5
样例输出：21
分析：
该题要注意的是，若每次不能合并M堆，则应该放在第一次合并时，因为当每次合并M堆到最后不够M堆时，还是需要再合并一次，导致总代价增加。而第一次选一合适的堆合并，以后每次都合并M堆，这样总代价最小
解法1：
堆排序
#include<iostream>
using namespace std;
int a[10001],ans=0;
void HeapDown(int root,int n)
{ int k;
while(root+root<=n)
{k=root+root;
if(k<n&&a[k]>a[k+1])k++;
if(a[k]<a[root])
{
swap(a[root],a[k]);
root=k;
}
else return;
}
}
void HeapDelete(int k)
{ swap(a[k],a[a[0]]);
a[0]--;
HeapDown(k,a[0]);//这里k固定为1,只需向下堆化
}
void HeapBuild(void)
{ for(int i=a[0]/2;i>=1;i--)
HeapDown(i,a[0]);
}
void Combine(int k)//合并K堆
{ if(k==0)return;
int newdata=0,i;
for(i=1;i<k;i++)//选堆顶累加，并删除堆顶，进行k-1次
{newdata+=a[1];
HeapDelete(1);
}
newdata+=a[1];//再选堆顶累加，并将累加数替换堆顶，向下堆化。
ans+=newdata;
a[1]=newdata;
HeapDown(1,a[0]);
}
int main()
{
int i,k;
scanf("%d%d",&a[0],&k);
for(i=1;i<=a[0];i++)
scanf("%d",&a[i]);
HeapBuild();
if((a[0]-1)%(k-1)!=0)
Combine((a[0]-1)%(k-1)+1);//计算第一次需要合并多少堆
while(a[0]>1) Combine(k);
cout<<ans;
}
解法2：hash,由于每个数的范围较小，则可用计数排序
#include<iostream>
using namespace std;
const int oo=0x7fffffff;
int n,m,ans=0,a[10005],b[10005]={0},p1=1,p2=1,cnt[200005]={0},max=20001;
bool flag=1;
/* p1初始指向a的第一个数
p2初始指向b的第一个数，b用来依次存放合并后产生的新数，这些数一定是升序的，b[0]表示b中有多少数*/
void Count_sort()//计数排序
{
for(int i = 1; i <= n; i++) cnt[ a[i]]++;
int z = 1;
for(int i =0; i <= max; i++)
for(int j = 0; j < cnt[ i ]; j++) a[z++] = i;
}
void Combine(int t)
{
int Min=0;
while( t--)
{
if( p1<=n)//a数组有数，从a,b两个数组里找最小
{
if( a[p1]>b[p2]&&p2<=b[0])Min+=b[p2++];//最小的在b里面
else Min+=a[p1++];//最小的数在a里面
}
else if(p2<=b[0])Min+=b[p2++];//只有b里面有数，直接在b中取
else {flag=0;break;}//a，b都没有数了
}
if(!flag)return;
b[++b[0]]=Min;ans+=Min;//将新数min放在b最后面
}
int main()
{
int i,t,p;
cin>>n>>m;
for( i=1;i<=n;i++)scanf("%d",&a[i]);
Count_sort();
if((n-1)%(m-1)!=0)Combine( (n-1)%(m-1)+1 );
while( flag )Combine(m);
cout<<ans;
return 0;
}