1412 {a} + {b}.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1412 {A} + {B}
Time Limit : 5000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
#include <iostream.h>
using namespace std;

const int nmMax=20000;
int num[nmMax]={0},temp[nmMax]={0},now;

int divFind(int find)
{
    int ca;
    for(ca=now-1;ca>=0;ca--)
    {
        if(num[ca]==find)
            return ca;
    }
    return -1;
}

int merge(int low,int mid,int high)//算法设计技巧与分析p.6
{
    int s=low,t=mid+1,k=low;
    int ca;
    while(s<=mid && t<=high)
    {
        if(num[s]<=num[t])
        {   temp[k]=num[s];s++;}
        else
        {   temp[k]=num[t];t++;}
        k++;
    }
    
    if(s==mid+1)
    {
        for(ca=k;ca<=high;ca++,t++)
            temp[ca]=num[t];
    }
    else
    {
        for(ca=k;ca<=high;ca++,s++)
            temp[ca]=num[s];
    }
    
    for(ca=low;ca<=high;ca++)
    {   num[ca]=temp[ca];}
    return 0;
}

int bottomSort()//p.9
{
    int s,t,i,n=now-1;

    t=1;//注意C是从0下标开始
    while(t<n)
    {
        s=t;t*=2;i=0;
        while(i+t-1<=n)
        {
            merge(i,i+s-1,i+t-1);
            i+=t;
        }
        if(i+s-1<n)
            merge(i,i+s-1,n);
    }
    return 0;
}

int main()
{
    int a,b,n,ca;

    while(cin>>a>>b)
    {
        now=1;
        cin>>num[0];
        for(ca=1;ca<a+b;ca++)
        {
            cin>>n;
            if(divFind(n)<0)
            {   num[now]=n;now++;}
        }
        
        bottomSort();
        for(ca=0;ca<now;ca++)
        {
            cout<<num[ca];
            if(ca<now-1)
                cout<<" ";
            else
                cout<<endl;
        }
    }
    return 0;
}