P1097 合并果子

Published on 2009 / 10 / 22

解法是每次取最小的两堆合并，N-1次后合并完成。

问题是每次取最小的两个数怎么找，我用双栈解决。

A是原来的数组，B是合并后的数组。开始读入以后给A一个快速排序，以后每次合并后存入B。

合并的最小两个数从A、B头取最小的数！

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
Accepted 有效得分：100 有效耗时：0ms

#include<stdio.h>

int N,As,Ae,Bs,Be;long Ans,A[20000],B[20000];

void KP(int st,int en)
{
    int a,b;long c;
    a=st,b=en,c=A[a];
    while(a<b)
    {
        while(a<b)
        {
            if(A[b]<c)
                {A[a]=A[b];break;}
            b--;
        }
        while(a<b)
        {
            if(A[a]>c)
                {A[b]=A[a];break;}
            a++;
        }
    }
    A[a]=c;
    if(st<a-1) KP(st,a-1);
    if(a+1<en) KP(a+1,en);
}

long Get()
{
    long a,b;
    a=100000000;b=100000000;
    if(As<Ae) a=A[As];
    if(Bs<Be) b=B[Bs];
    if(a<b) 
        {As++;return a;}
    else
        {Bs++;return b;}
}

int main()
{
    scanf("%d",&N);
    int a,b;
    for(a=0;a<N;a++)
        scanf("%ld",&A[a]);
    KP(0,N-1);Ae=N;
    for(a=1;a<N;a++)
        {B[Be]=Get()+Get();Ans+=B[Be];Be++;}
    printf("%ld\n",Ans);
    return 0;
}