http://acm.pku.edu.cn/JudgeOnline/problem?id=3253
这是一个哈夫曼数的简单例子，算法很简单，但提交了很多次才ac，但每一个版本都有很多收获。
1.利用Java的集合类以及排序的方法，简单的实现其中的排序，将所有的num添加到集合中，然后排序，提取第1.2个元素，然后相加，删除这两个元素，添加这两个元素的和，然
后排序，直到集合的元素个数给1.
另外，在该程序中使用了jdk1.5支持的输入，大大简化了输入：
Scanner cin = new Scanner(System.in);
int count = cin.nextInt();
核心的代码如下：
Collections.sort(array);
int sum=0,a,b;
while(array.size()!=1){
a = array.get(0);
b = array.get(1);
array.add(a+b);
array.remove(0);
array.remove(1);//注意这里不是1，因为删除一个后集合原来的第1个元素变为了第0个元素
sum += a+b;
Collections.sort(array);
}
System.out.println(sum);
但是这个实现虽然简单，但超时，运行需要2s多，而题目要求1s
2.为了避免排序，采用空间换时间的策略.想法是这样的：建立一个数组length[]，该数组的第i个元素表示：集合中有该元素的个数，然后从小到大选出最小的a和b，将length
[a]--,length[b]--,length[a+b]++,直到数组中没有非零元素.
核心代码如下：
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
length[temp]++;
}
for(i=1;i<n;i++)
{
while(!length[j])
j++;
a=j;
length[j]--;
while(!length[j])
j++;
b=j;
length[j]--;
length[a+b]++;
sum += a+b;
}
结果运行中错误，原因是数组开的不够大，题目要求有20000个数字，每个数字最大为50000，如果要满足题目要求length长度为50000*20000，无法开如此大的数组.
3.由于数组中有大量的插入和删除的操作，准备采用链表存储，输入的结果是一个由小到大排列的链表，然后删除前两个数字，插入两个数字的和，按顺序插入到链表中.
核心代码如下：
但是依然超时.
for(i=1;i<=n;i++)
{
//动态分配待插入节点存储空间
struct LNode* p_insert=(struct LNode*)malloc(sizeof(struct LNode));
scanf("%d",&p_insert->data);
p_head=head;
//插入前链表为空
if(head->next==NULL)
{
p_head->next=p_insert;p_insert->next=NULL;
}
else
{
//查找该插入的地方
while(p_head->data<p_insert->data&&p_head->next!=NULL)
{
p_temp=p_head;
p_head=p_head->next;
}
//不是插入到链表结尾
if(p_head->data>=p_insert->data)
{
p_temp->next=p_insert;
p_insert->next=p_head;
}
//插入到链表结尾
else
{
p_head->next=p_insert;
p_insert->next=NULL;
}
}
}
//依此删除前两个数字，并插入两个数字的和
for(i=1;i<n;i++)
{
struct LNode* a=head->next;
struct LNode* b=head->next->next;
struct LNode* c=(struct LNode*)malloc(sizeof(struct LNode));
sum+=a->data+b->data;
c->data=a->data+b->data;
head->next=b->next;
free(a);
free(b);
p_head=head;
//查找该插入的地方
while(p_head->data<c->data&&p_head->next!=NULL)
{
p_temp=p_head;
p_head=p_head->next;
}
//不是插入到链表结尾
if(p_head->data>=c->data)
{
p_temp->next=c;
c->next=p_head;
}
//插入到链表结尾
else
{
p_head->next=c;
c->next=NULL;
}
}
printf("%d/n",sum);
4.利用qsort利用数组实现.
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )
输入后排序,然后插入两个数字的和，按顺序插入到数组中.
核心代码如下:
插入时的排序语句可以用qsort(array,n,sizeof(int),comp);代替，但效率一定会低，因为所有元素排序效率会很低，因为只有一个元素是没有排序的
终于ac了!
带有详细注释的代码可以从http://download.csdn.net/user/china8848/获得。
for(i=0;i<n;i++)
scanf("%d",&array[i]);
//对原始数列排序
qsort(array,n,sizeof(int),comp);
//插入两个元素的和
for(i=1;i<n;i++)
{
array[i]+=array[i-1];
sum+=array[i];
temp=array[i];
for(j=i+1;j<n;j++)
{
if(temp>array[j])
array[j-1]=array[j];
else
break;
}
array[j-1]=temp;
}
printf("%I64d/n",sum);