显然这是道贪心题
关键是怎么贪,第一想法是根据数字的大小从大到小排列,显然不行。
这里是要组成字符串,所以要根据两者形成的字符串来从小到大排列。
具体视频可以看左神的初级算法课程
注意点:
第一个数字不能是0,所以要进行判断,也有可能第一个子数据全是0,同理也可能是前两个串都为0,最终,所有串都可能为0,如果一般的程序,此时没有任何输出。但是第三个测试点是,在所有数据都是0的情况下,需要输出一个0。
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(string a, string b){
return a+b < b+a;
}
int main(){
string s;
int n;
scanf("%d",&n);
vector<string> v;
for(int i=0;i<n;i++){
cin>>s;
v.push_back(s);
}
sort(v.begin(),v.end(),cmp);
int flag = 0;
for(int i=0;i<v.size();i++){
if(flag==0){
for(int j=0;j<v[i].size();j++){
if(flag==0 && v[i][j]=='0') {
continue;
}
else {
flag=1;
printf("%c",v[i][j]);
}
}
}else
cout<<v[i];
}
if(flag==0) cout<<"0";
cout<<endl;
return 0;
}