Description

在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。

Input

第1 行有2 个正整数n和k，表示有n堆石子，每次至少选2 堆最多选k堆石子合并。第2 行有n个数，分别表示每堆石子的个数。

Output

计算出的最大总费用和最小总费用。

Sample Input


7 3
45 13 12 16 9 5 22

Sample Output


593 199







#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int a[100005],b[100005],n,c,mn,mx,k,num;

void sift( int i, int m)
{    int k=2*i;
    a[0]=a[i];
    while( k<=m )
    {    if( k<m && a[k+1]>a[k] ) k++;
        if( a[0]<a[k] )
        {    a[i]=a[k];
            i=k;
            k=2*i;
        }
        else break;
    }
    a[i]=a[0];
}

void heapSort()
{    int j;
    for( j=n/2; j>=1; j-- ) sift( j, n);
    for( j=n; j>=2; j--)
    {    a[0]=a[j];
        a[j]=a[1];
        a[1]=a[0];
        sift( 1, j-1);
    }
}

void min()
{
    int i,p=0,j=0;
    if (k>=num)
    {
        for (i=1;i<=num;i++)
            mn+=a[i];
    }
    else
    {
        for (i=1;i<=k;i++)
            p+=a[i];
        mn+=p;
        for (;i<=num;i++)
            a[++j]=a[i];
        a[++j]=p;
        num=j;
        sort(&a[1],&a[num+1]);
        min();
    }
}


void max()
{
    int i,p=0;
    if (num<=2)
    {
        for (i=num;i>=1;i--)
            mx+=a[i];
    }
    else
    {
        p=a[num]+a[num-1];
        mx+=p;
        num-=2;
        a[++num]=p;
        max();
    }

}

int main()
{
    int i;
    scanf ("%d%d",&n,&k);
    num=n;
    for (i=1;i<=n;i++)
        scanf ("%d",&a[i]);
    heapSort();
    for (i=1;i<=n;i++)
        b[i]=a[i];
    min();
    for (i=1;i<=n;i++)
        a[i]=b[i];
    num=n;
    max();
    printf ("%d %d",mx,mn);
    return 0;
}

忘了补充了，所有测试数据最大值都对，就最小值不对。
最大是每次都把最大的两堆加起来，

谢谢了，可是你的运行会错误呀，其中一个最小的测试数据

1000 7
1 67 76 97 70 67 6 23 41 11 43 97 74 82 99 74 84 85 86 39 63 65 94 84 44 97 19 7 95 42 14 94 29 7 17 41 39 31 83 49 62 73 72 20 94 97 70 76 34 90 88 92 18 44 84 70 49 89 53 23 88 29 75 52 53 90 34 64 6 49 10 82 59 96 50 48 73 21 10 93 52 9 43 92 9 72 26 85 88 18 88 95 38 95 9 93 24 79 57 95 22 68 91 44 23 41 79 1 48 24 94 30 23 19 86 40 18 1 80 53 58 26 33 41 93 56 85 33 7 55 28 89 64 83 4 20 33 7 31 82 2 56 37 89 3 78 39 3 47 39 84 5 6 69 12 23 3 15 54 30 1 28 13 29 37 68 97 35 73 37 7 52 45 39 69 26 43 63 64 98 81 45 45 17 91 85 65 15 19 69 91 98 32 41 85 41 90 4 81 81 2 36 17 73 45 45 16 75 90 12 59 49 52 18 19 31 54 81 62 66 36 99 39 74 21 23 5 2 9 94 67 86 54 7 62 29 54 75 8 88 45 73 6 81 66 74 38 19 90 28 42 8 91 32 9 92 63 90 18 45 42 39 53 43 61 53 33 3 1 72 6 86 87 7 21 77 16 65 28 12 41 25 80 84 67 97 27 32 3 52 39 30 13 39 82 92 86 38 75 58 19 74 42 53 66 18 16 28 98 12 24 66 92 15 50 31 45 76 87 42 50 88 56 33 66 84 33 9 28 87 34 9 43 9 52 28 85 70 74 9 60 93 35 25 27 99 71 15 48 91 22 81 53 55 44 67 95 53 81 30 19 18 17 33 22 46 29 41 38 4 85 75 72 43 28 2 69 49 62 7 87 14 69 53 41 66 26 10 83 41 6 17 5 40 28 25 77 97 58 15 79 15 84 38 60 40 20 28 95 98 8 95 47 89 89 28 31 25 79 88 27 75 81 49 78 85 81 17 91 92 92 85 68 63 36 36 54 49 2 25 38 18 90 47 67 2 29 54 42 14 3 99 50 75 10 44 34 12 46 47 32 89 83 9 80 37 71 58 97 84 94 48 70 53 17 14 84 7 1 54 99 50 40 32 37 74 51 4 57 13 20 7 6 34 29 35 71 37 44 92 94 59 87 21 12 61 17 81 19 10 52 22 44 96 47 51 67 47 52 18 87 62 38 5 88 43 73 34 3 41 57 49 99 70 94 53 91 57 90 23 5 67 60 60 96 45 83 64 94 27 76 22 36 6 13 36 31 12 84 50 33 38 46 24 24 12 49 35 84 21 39 78 6 41 15 66 39 18 59 12 79 58 72 31 55 24 52 73 9 11 66 49 89 49 75 19 55 99 83 19 51 71 26 86 17 61 21 18 60 29 62 81 32 61 18 6 97 12 82 2 58 88 19 63 68 39 66 55 41 26 60 97 45 35 8 21 73 61 32 86 72 75 28 33 6 32 49 91 10 43 85 76 61 23 53 23 56 29 90 10 36 62 91 89 95 48 30 5 17 80 13 72 50 47 97 21 96 24 52 49 22 3 59 12 46 35 12 46 61 12 52 14 5 90 62 39 77 70 81 74 3 95 87 61 95 14 75 39 52 82 39 78 5 96 41 3 6 1 59 66 42 57 93 17 61 26 11 10 82 91 32 50 36 56 9 39 81 73 48 35 78 98 34 72 28 10 36 54 36 38 17 31 33 37 16 48 61 23 38 5 51 35 8 39 31 31 28 53 27 8 20 56 97 29 42 25 93 53 20 22 94 45 43 60 71 75 90 34 21 83 57 55 25 10 79 7 2 39 96 41 74 31 69 62 25 57 40 27 4 63 12 6 86 33 37 89 21 72 12 19 84 26 19 6 19 58 74 80 75 36 43 40 48 77 40 23 13 86 49 20 80 58 91 12 96 29 46 81 71 5 39 99 5 74 6 75 9 29 24 7 79 59 85 26 21 29 58 57 17 39 46 2 5 57 61 35 80 93 16 58 56 94 8 51 35 62 63 9 81 53 85 69 12 71 19 16 2 41 43 16 81 51 18 94 47 91 20 67 89 78 15 62 78 78 46 67 54 86 70 66 58 94 32 65 84 94 49 87 58 6 36 24 53 73 40 99 53 24 73 12 83 67 14 67 22 7 13 58 20 77 63 97 82 4 5 59 95 4 93 9 65 78 52 66 8 82 56 26 30 50 89 23 25 76 4 46 93 43 32 56 15 72 24 58 94 76 34 10 34 39 1 55 86 57 28 64 1 13 97 28

谢谢你，可是你这个最小值答案会偏小、、、、

测试数据
1000 7
1 67 76 97 70 67 6 23 41 11 43 97 74 82 99 74 84 85 86 39 63 65 94 84 44 97 19 7 95 42 14 94 29 7 17 41 39 31 83 49 62 73 72 20 94 97 70 76 34 90 88 92 18 44 84 70 49 89 53 23 88 29 75 52 53 90 34 64 6 49 10 82 59 96 50 48 73 21 10 93 52 9 43 92 9 72 26 85 88 18 88 95 38 95 9 93 24 79 57 95 22 68 91 44 23 41 79 1 48 24 94 30 23 19 86 40 18 1 80 53 58 26 33 41 93 56 85 33 7 55 28 89 64 83 4 20 33 7 31 82 2 56 37 89 3 78 39 3 47 39 84 5 6 69 12 23 3 15 54 30 1 28 13 29 37 68 97 35 73 37 7 52 45 39 69 26 43 63 64 98 81 45 45 17 91 85 65 15 19 69 91 98 32 41 85 41 90 4 81 81 2 36 17 73 45 45 16 75 90 12 59 49 52 18 19 31 54 81 62 66 36 99 39 74 21 23 5 2 9 94 67 86 54 7 62 29 54 75 8 88 45 73 6 81 66 74 38 19 90 28 42 8 91 32 9 92 63 90 18 45 42 39 53 43 61 53 33 3 1 72 6 86 87 7 21 77 16 65 28 12 41 25 80 84 67 97 27 32 3 52 39 30 13 39 82 92 86 38 75 58 19 74 42 53 66 18 16 28 98 12 24 66 92 15 50 31 45 76 87 42 50 88 56 33 66 84 33 9 28 87 34 9 43 9 52 28 85 70 74 9 60 93 35 25 27 99 71 15 48 91 22 81 53 55 44 67 95 53 81 30 19 18 17 33 22 46 29 41 38 4 85 75 72 43 28 2 69 49 62 7 87 14 69 53 41 66 26 10 83 41 6 17 5 40 28 25 77 97 58 15 79 15 84 38 60 40 20 28 95 98 8 95 47 89 89 28 31 25 79 88 27 75 81 49 78 85 81 17 91 92 92 85 68 63 36 36 54 49 2 25 38 18 90 47 67 2 29 54 42 14 3 99 50 75 10 44 34 12 46 47 32 89 83 9 80 37 71 58 97 84 94 48 70 53 17 14 84 7 1 54 99 50 40 32 37 74 51 4 57 13 20 7 6 34 29 35 71 37 44 92 94 59 87 21 12 61 17 81 19 10 52 22 44 96 47 51 67 47 52 18 87 62 38 5 88 43 73 34 3 41 57 49 99 70 94 53 91 57 90 23 5 67 60 60 96 45 83 64 94 27 76 22 36 6 13 36 31 12 84 50 33 38 46 24 24 12 49 35 84 21 39 78 6 41 15 66 39 18 59 12 79 58 72 31 55 24 52 73 9 11 66 49 89 49 75 19 55 99 83 19 51 71 26 86 17 61 21 18 60 29 62 81 32 61 18 6 97 12 82 2 58 88 19 63 68 39 66 55 41 26 60 97 45 35 8 21 73 61 32 86 72 75 28 33 6 32 49 91 10 43 85 76 61 23 53 23 56 29 90 10 36 62 91 89 95 48 30 5 17 80 13 72 50 47 97 21 96 24 52 49 22 3 59 12 46 35 12 46 61 12 52 14 5 90 62 39 77 70 81 74 3 95 87 61 95 14 75 39 52 82 39 78 5 96 41 3 6 1 59 66 42 57 93 17 61 26 11 10 82 91 32 50 36 56 9 39 81 73 48 35 78 98 34 72 28 10 36 54 36 38 17 31 33 37 16 48 61 23 38 5 51 35 8 39 31 31 28 53 27 8 20 56 97 29 42 25 93 53 20 22 94 45 43 60 71 75 90 34 21 83 57 55 25 10 79 7 2 39 96 41 74 31 69 62 25 57 40 27 4 63 12 6 86 33 37 89 21 72 12 19 84 26 19 6 19 58 74 80 75 36 43 40 48 77 40 23 13 86 49 20 80 58 91 12 96 29 46 81 71 5 39 99 5 74 6 75 9 29 24 7 79 59 85 26 21 29 58 57 17 39 46 2 5 57 61 35 80 93 16 58 56 94 8 51 35 62 63 9 81 53 85 69 12 71 19 16 2 41 43 16 81 51 18 94 47 91 20 67 89 78 15 62 78 78 46 67 54 86 70 66 58 94 32 65 84 94 49 87 58 6 36 24 53 73 40 99 53 24 73 12 83 67 14 67 22 7 13 58 20 77 63 97 82 4 5 59 95 4 93 9 65 78 52 66 8 82 56 26 30 50 89 23 25 76 4 46 93 43 32 56 15 72 24 58 94 76 34 10 34 39 1 55 86 57 28 64 1 13 97 28

32693122 173977

疾风是我室友，那个偶素数就是我用他的号发的。嘿嘿。可是我不懂为什么我的代码会错误，我虽然没有一个一个加起来，但是我调试过是每次加k个，但是最后结果就是错了，很郁闷

我是sunny lover

这个最大值是怎么求的啊？先从小道大排序，然后第0个*1，第1个*2.。。。。。

int Max(int *a, int n)
{
    int sum = 0, i;
    for(i = 0; i < n; i++)
        sum += a[i] * (i + 1);
    sum -= a[n - 1];//以上三行不太懂
    return sum;
}

我是最大值对着呢，就最小值不对

谢谢了，偶素数那个题已经懂了，能麻烦你把求最小值的思路告诉我吗？我开始写的思路是对，但是结果不对。你给我的程序算法有点看不懂。证明也行，最大值的证明我已经知道了。谢谢了