PAT甲级1038.

目录

A1038

题目

样例

样例1

输入:

5 32 321 3214 0229 87

输出:

22932132143287

补充样例1

输入:

7 32 321 3214 0229 87 00 000

输出:

22932132143287

补充样例2

输入:

2 00 000

输出:

0

思路和坑点

　　每一个数按照string类存储，然后按照string类a+b<b+a的原则进行排序，并最终输出。
　　简单证明：
　　对于两个字符串而言，如果组成最小数，则a+b<b+a的规则进行组和，组合成的数是最小的，如果将这个组和视为一个字符串和另外一个字符串仍然按照这种方式进行组和还会得到最小的。
　　坑点
　　首先是开头不能为0，不能只对第一个字符串进行判定，可能第一个串全是0.有以下两种方法可以解决：一、把所有的结果连成一个字符串进行判定输出。二、按照二维数组的方式进行单个字符的扫描，从遇到的第一个非0字符开始输出。
　　注意全是0的情况下，只需输出0。（见补充样例）

AC代码

#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){            //排序规则 
    return a+b<b+a;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    vector<string> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    sort(v.begin(),v.end(),cmp);
    int tag=0;                            //tag为遇到第一个非0的时候的标记，遇到了改为1 
    for(int i=0;i<n;i++){                //二维扫描输出 
        for(int j=0;j<v[i].size();j++){
            if(tag==0&&v[i][j]=='0')
                continue;
            else
                tag=1;
            putchar(v[i][j]);
        }
    }
    if(tag==0) cout<<0;                    //如果全是0，则输出0 
    return 0;
}