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;
}

楼主，那个最大值是怎么算出来的？我想最大值应该不是那个

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

#include <stdio.h>
#include <queue>
using namespace std;

struct minint
{
    int weight;
    bool operator <(minint a)const
    {
        return weight >= a.weight;
    }
};
struct maxint
{
    int weight;
    bool operator <(maxint a)const
    {
        return weight <= a.weight;
    }
};

int main()
{
    int n,k;
    int i,j;
    while(EOF != scanf("%d %d",&n,&k))
    {
        priority_queue<minint> qmin;
        priority_queue<maxint> qmax;
        minint min;
        maxint max;
        while(n--)
        {
            scanf("%d",&min.weight);
            max.weight = min.weight;
            qmin.push(min);
            qmax.push(max);
        }
        int sum = 0;
        while(1 != qmin.size())
        {
            int tempsum = 0;
            for(i = 0;i<k && !qmin.empty();i++)
            {
                minint temp = qmin.top();
                tempsum += temp.weight;
                qmin.pop();
            }
            min.weight = tempsum;
            qmin.push(min);
            sum+=tempsum;
        }
        printf("%d ",sum);
        sum = 0;
        while(1 != qmax.size())
        {
            int tempsum = 0;
            for(i = 0;i<2 && !qmin.empty();i++)
            {
                maxint temp = qmax.top();
                tempsum += temp.weight;
                qmax.pop();
            }
            max.weight = tempsum;
            qmax.push(max);
            sum+=tempsum;
        }
        printf("%d\n",sum);
    }
    return 0;
}

/*
7 3
45 13 12 16 9 5 22
5 9 12 13 16 22 45
26 51 45
26 + 51 + 122
5 117
67 + 83 + 96 + 108 + 117 + 122
*/

抢个位置 为了你的题我和李志同学讨论了一下午  抢在他前面  一会他就该来了

[ 本帖最后由 laoyang103 于 2011-7-31 18:49 编辑 ]

收到的鲜花

• qazujm1212 于 2011-08-01 17:01 送鲜花  5朵  

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

int asc(const void * p1, const void * p2) {
    return *(int *)p1 - *(int *)p2;
}

int desc(const void * p1, const void * p2) {
    return *(int *)p2 - *(int *)p1;
}

int main(void) {
    int min = 0, max = 0;
    int n, k, i, j, h, count, temp, * pNums, * pNums_temp;
//    freopen("test.txt", "r", stdin);
    scanf("%d%d", &n, &k);
    assert(n > 1 && k > 1 && k <= n);
    count = n;
    pNums = (int *)malloc(sizeof(int) * n);
    for(i = 0; i < n; i++)
        scanf("%d", pNums + i);

    qsort(pNums, n, sizeof(int), desc);
    temp = pNums[0];
    for(i = 1; i < n; i++)
        max += temp += pNums[i];

    while(count > 1) {
        qsort(pNums, count, sizeof(int), asc);
        pNums_temp = (int *)malloc(sizeof(int) * (count / k + 1));
        for(i = 0, h = 0; i < count; ) {
            temp = 0;
            for(j = 0; j < k && i < count; j++)
                temp += pNums[i++];
            if((count % k == 0 && i == count) || i < count)
                min += temp;
            pNums_temp[h++] = temp;
        }
        free(pNums);
        pNums = pNums_temp;
        count = h;
    }

    printf("%d %d\n", max, min);
    free(pNums);
    return 0;
}

改了一下，现在可以了吗？

[ 本帖最后由 lz1091914999 于 2011-7-31 19:40 编辑 ]

收到的鲜花

• qazujm1212 于 2011-08-01 17:02 送鲜花  5朵  

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

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

楼主也是福建农大的么？认识疾风么？
问题其实很简单，比较郁闷的是题目的取值范围很不明确。害我提交了几次总是WA还以为是逻辑有问题呢。
这是AC的代码。和那个合并果子属于一个级别的问题。

#include <stdio.h>

#define MAX_SIZE    100000

int S[MAX_SIZE], N, K;

void HeapSort(int *a, int n)
{
    int i, p, k, k1, k2, tmp;

    for (i = 1; i < n; i++)
    {
        p = i;
        k = (i - 1) >> 1;
        while (k >= 0)
        {
            if (a[k] < a[p]){ tmp = a[k]; a[k] = a[p]; a[p] = tmp;}
            p = k;
            k = (p - 1) >> 1;
        }
    }
    for (i = n - 1; i > 0; i--)
    {
        tmp = a[0]; a[0] = a[i]; a[i] = tmp;
        p = 0;
        k1 = (p << 1) + 1;
        k2 = k1 + 1;
        while (k1 < i)
        {
            k = (k2 < i && a[k2] > a[k1]) ? k2 : k1;
            if (a[k] < a[p]) break;
            tmp = a[p]; a[p] = a[k]; a[k] = tmp;
            p = k;
            k1 = (p << 1) + 1;
            k2 = k1 + 1;
        }
    }
}



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;
}

int Min(int *a, int n, int k)
{
    int sum = 0, b[MAX_SIZE], bn = 0, i, j, t, c;
    c = (n - 1) % (k - 1);
    if(c)
    {
        for(i = 0, t = 0; i <= c; t += a[i++]);
        sum = t;
        b[bn++] = t;
    }
    for(j = 0; n - i + bn - j > 1;)
    {
        for(c = 0, t = 0; c < k; c++)
        {
            if(i == n) t += b[j++];
            else if(j == bn) t += a[i++];
            else t += (a[i] < b[j]) ? a[i++] : b[j++];
        }
        sum += t;
        b[bn++] = t;
    }
    return sum;
}

int main()
{
    int i;
    scanf("%d%d\n", &N, &K);
    for(i = 0; i < N; i++)
        scanf("%d", S + i);
    HeapSort(S, N);
    printf("%d %d\n", Max(S, N), Min(S, N, K));
    return 0;
}

收到的鲜花

• qazujm1212 于 2011-08-01 17:02 送鲜花  5朵