|
最优合并问题 Time Limit:1000MS Memory Limit:65536K Description 给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。 Input 输入数据的第一行有1 个正整数k（k≤1000），表示有k个待合并序列。接下来的1 行中，有k个正整数，表示k个待合并序列的长度。 Output 输出两个整数，中间用空格隔开，表示计算出的最多比较次数和最少比较次数。 Sample Input 4
Sample Output 78 52
Source |
此问题思路很简单，当取最小值保证每次的2个加数为最小便可，最大值同理取当前最大的两个值便可
由于取最小值与取最大值实现的方式不同这里简单介绍一下
最小值不需要排序，因为排序也没用
请看下面序列
3,6,5,12,7
如果排好序之后依次按照，找最小连个数进行相加
排好序之后3,5,6,7,12
最小值3+5 = 8 8,6,7,12 按照排序的思路此时不能保证当前数组中前两位是最小值，所以还要排序
6,7,8,12 6+7 = 13 -->13,8,12
继续排序中。。。
按照以上思路比较耗时
其实我的思路很简单，每次不就是取2个当前数组中的最小值嘛，申请2个变量不就行了，保证每次2个变量中的值值是当前的最小值便可
int a,b;
3,6,5,12,7
a = 3,b = 5; min +=8;
将3,6,5,12,7修改成8,6,2147483647,12,7 将2个数合并之后必有一个数取消在数组中的位置，不妨将此数改成一个较大的数，将此空间和谐掉
8,6,2147483647,12,7
a = 6,b = 7 min += 13 8,2147483647,2147483647,12,13
a = 8,b = 13 min += 21 2147483647,2147483647,2147483647,21,13
a = 21,b = 13 min +=34
最后按照题意m和n的序列需要m+n-1 次比较
min -= (n -1)
这样便求出了最小值
最大值简单，将数组从大到小排列仍然是3,6,5,12,7
12,7,6,5,3
依次相加前两位便可
12+7 max +=19;
12,19,6,5,3
19+6 max += 25;
12,19,25,5,3
.......
代码如下：
View Code
#include<stdio.h>
#include<stdlib.h>
int main()
{
int num,min,max,*arrmax,*arrmin,i,j,a,b,k,temp;
scanf("%d",&num);
arrmax = (int *)malloc(num * sizeof(int));
arrmin = (int *)malloc(num * sizeof (int));
for(i = 0; i < num;i++)
{
scanf("%d",&arrmax[i]);
arrmin[i] = arrmax[i];
}
for(min = i = 0; i < num - 1; i++)//一共进行num - 1此比较
{
a = 0,b = 1;//数组编号
for(j = 2; j < num;j++)
{
if(arrmin[j] < arrmin[a] || arrmin[j] < arrmin[b])
{
if(arrmin[a] > arrmin[b])
a = j;
else
b = j;
}
}
min += (arrmin[a] + arrmin[b]);
arrmin[a] +=arrmin[b];
arrmin[b] = 2147483647;
}
min -=(num - 1);
for(i = 0; i < num;i++)
{
for(k = i,j = i + 1; j < num;j++)
if(arrmax[k] < arrmax[j])
k = j;
temp = arrmax[k];
arrmax[k] = arrmax[i];
arrmax[i] = temp;
}
for(max = i = 0; i < num - 1;i++)
{
max +=(arrmax[i] + arrmax[i + 1]);
arrmax[i + 1] +=arrmax[i];
}
max -= (num - 1);
printf("%d %d\n",max,min);
return 0;
}