【PAT_1038】Recover the Smallest N

题目描述

给定一组数字段，从它们中恢复最小的数字。 例如，给定{32,321,3214,0229,87}，我们可以恢复许多数字，例如32-321-3214-0229-87或0229-32-87-321-3214，关于不同的组合顺序 这些段，最小的数字是0229-321-3214-32-87。

输入

数字段个数N 之后是N个数字段

输出

输出最小得数字段组合，并将去除开头得零

解题思路

本题得实际意思就是获得一组数字得最小值得组合。考虑用string类型存储数字段。
使用sort排序，其中cmp（）返回得应该为s1+s2<s2+s1;必须保证两个数字段组合起来得到得数字是最小得

代码

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int cmp1(string s1, string s2) {
  return s1+s2<s2+s1;
}
int main() {
    int n;
    scanf("%d", &n);
    vector<string> datas(n);
    for (int i = 0; i < n; i++) {
        cin >> datas[i];
    }
    sort(datas.begin(), datas.end(), cmp1);
    bool flag = false;
    for (int i = 0; i < n; i++) {
        if (!flag) {
            for (int j = 0; j < datas[i].size(); j++) {
                if (datas[i][j] == '0' && !flag) {
                    continue;
                }
                else {
                    flag = true;
                    cout << datas[i][j];
                }
            }
        }
        else {
            cout << datas[i];
        }
    }
    if(!flag)cout<<0<<endl;
    return 0;
    }