PAT_A 1038. Recover the Smallest Number (30)

PAT_A 1038. Recover the Smallest Number (30)

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:

Each input file contains one test case. Each case gives a positive integer N (<=10000) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the smallest number in one line. Do not output leading zeros.

Sample Input:
    5 32 321 3214 0229 87
Sample Output:
    22932132143287

• 题目分析：
  
  • 给定一组数，每个数不超过8digits,且是正数。通过这几组数进行任意组合，使最终的组合数最小。
    如　 {32, 321, 3214, 0229, 87}　最小的是：0229-32-87-321-3214
  • 解决分两步：
    1.a,b 两两组合，比较大小如　ab和ba比，当ab　< ba ，将b挂在a的右子树，否则挂在左子树。
    2.二叉树构建完成后，中序遍历二叉树。
  • 注意：
    1.组合数开始的0不输出，如　003,应输出3
    2.如果组合数全书0,则要输出一个0(2`测试点)
  • 错误思路：两两比较，直接排序输出–没有考虑全，丢失比较数据，造成不是最小
• code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
typedef vector<int> vint;
vint vsmall;
//is ab<ba
bool isSmall(vint a,vint b)
{
    int tmpa,tmpb;
    int sizea=a.size();
    int sizeb=b.size();
    for(int i=0;i<sizea+sizeb;i++)
    {
        if(i<sizea)
          tmpa=a[i];
        else if(i<sizea+sizeb)
          tmpa=b[i-sizea];

        if(i<sizeb)
          tmpb=b[i];
        else if(i<sizeb+sizea)
          tmpb=b[i-sizeb];
        if(tmpa<tmpb)
          return true;
        else if(tmpa>tmpb)
          return false;
    }
}
//二叉排序树
struct  bcomp
{
    vint tmp;
    bcomp *left=NULL;
    bcomp *right=NULL;
};
bcomp *head=NULL;
void insert(bcomp*root,bcomp*tmp)
{
    if(isSmall(root->tmp,tmp->tmp))
    {
        if(root->right==NULL)
          root->right=tmp;
        else
          insert(root->right,tmp);

    }else
    {
        if(root->left==NULL)
          root->left=tmp;
        else
          insert(root->left,tmp);
    }
}
void build(bcomp n)
{
    bcomp *btmp=new bcomp();//为方便AC，不delete操作
    btmp->tmp=n.tmp;
    if(head==NULL)
        head=btmp;
    else
        insert(head,btmp);
}
int zero=0;//处理不输出开头的0，如002，应是2
int allbits=0;//控制总位数，处理特殊情况，全是0，如000要输出0
void show(bcomp *root)
{
    if(root==NULL)
        return;
    show(root->left);
    for(int j=0;j<root->tmp.size();j++)
    {
        if(zero>0)
          cout<<root->tmp[j];
        else if(root->tmp[j]>0)
        {
          cout<<root->tmp[j];
          zero++;
        }else if(zero+1==allbits)
          cout<<root->tmp[j];
        //这绝对是坑点
        allbits--;
    }
    show(root->right);
}
int main()
{
    //freopen("in","r",stdin);
    int N,tmp;
    vint vtmp;
    cin>>N;
    string stri;
    bcomp btmp;
    for(int i=0;i<N;i++)
    {
        cin>>stri;
        allbits+=stri.length();
        for(int j=0;j<stri.length();j++)
            vtmp.push_back(stri[j]-'0');
        btmp.tmp=vtmp;
        build(btmp);
        vtmp.clear();
    }
    show(head);
    return 0;
}

• AC