PAT甲级1038 组成最小数

╰半橙微兮° 2023-06-26 12:22 9阅读 0赞

> 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 (≤10  
> 4  
>  ) 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. Notice that the first digit must not be zero.

> Sample Input:  
> 5 32 321 3214 0229 87

> Sample Output:  
> 22932132143287

题意：给你N个数，任意组合在一起，使得最后组成的数最小，输出这个数，注意这个数字前面的0舍去，即0012234输出结果是12234

##### 初次挑战代码： #####

每个数字用字符串处理，按首字母分类装入map，然后按照字母序大小排序，如果两个字符不等长的话，将较小的那个填充为等长，填充字符是最后一个字符

#include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<algorithm>
    using namespace std;
    bool cmp(string a,string b)
    { 
        string ss;
        if(a.size()<b.size())//将两字符串变成等长
        { 
            char x=a[a.size()-1];
            ss=a;
            for(int i=a.size();i<b.size();i++)
            ss+=x;
            return ss<b;
        }
        else if(a.size()>b.size())
        { 
            char x=b[b.size()-1];
            ss=b;
            for(int i=b.size();i<a.size();i++)
            ss+=x;
            return a<ss;
        }
        return a<b;
    }
    int main()
    { 
        int n;
        string s;
        cin>>n;
        map<int,vector<string> > mm;
        for(int i=0;i<n;i++)
        { 
            cin>>s;
            mm[s[0]-'0'].push_back(s);
        }
        for(int i=0;i<=9;i++)//排序
        { 
            sort(mm[i].begin(),mm[i].end(),cmp);
        }
        int cnt=0;
        for(int i=0;i<mm[0].size();i++)
        { 
            if(cnt==0)cout<<stoi(mm[0][i]);
            else cout<<mm[0][i];   
            if(stoi(mm[0][i])>0)cnt++; 
        }
        for(int i=1;i<=9;i++)
        { 
            if(mm[i].size()!=0)
            { 
                for(int j=0;j<mm[i].size();j++)
                { 
                    cout<<mm[i][j];
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
就拿了23分，思路不够完善  
之后看了大佬们的方法，学习到了很多  
1.首先对于排序，不是拘泥于两两字符串之间，而是把a,b的组合看作一个整体，如果a+b<b+a，那么a之后跟上b就是更优解，交换a,b,依次类推，到最后不能再有任何交换，便是最终结果  
2.输出的时候不要一个个字符串输出，将每个字符串先拼接起来，然后去除前面的0，最后在输出，我最早的时候在这个方面想的太简单了  
3.利用的是sort自定义排序，让计算机暴力运算，不过好像时间花费要多很多，64ms，差不多是我原来那个笨方法的四倍时间

##### AC代码 #####

#include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    using namespace std;
    bool cmp(string a,string b)
    { 
        return a+b<b+a;
    }
    int main()
    { 
        int n;
        string s;
        cin>>n;
        vector<string> mm;
        for(int i=0;i<n;i++)
        { 
            cin>>s;
            mm.push_back(s);
        }
        sort(mm.begin(),mm.end(),cmp);
        string output="";
        for(int i=0;i<n;i++)output+=mm[i];
        int flag=1;//出现第一个不是0的数，标记为0
        for(int i=0;i<output.size();i++)
        { 
            if(flag==1&&output[i]!='0')flag=0;
            if(!flag)cout<<output[i];
        }
        if(flag==1)cout<<0;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200101191222852.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200102143252358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70