题目

设有n个正整数（n ≤ 20），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

  • 大意
    将一串数字排序，最后首尾相连，组成一个最大的数
  • 思路
    • 显然，最高位越大的排在越前面；
    • 若最高为相同，则应该比较“谁排在谁前面更大”。

      比如：数字A = 312， 数字B= 323
      即有两种情况：
      1.A排在B前面: 312323
      2.B排在A前面: 323312
      显然，B排在A前面 数更大

  • 注意
    • 两位数和三位数谁在前谁在后，都用以上方法比较
  • 代码
    #include<iostream>
#include<algorithm>
using namespace std;
string str[22];
bool judge(string a, string b){//按最高位排序
  return (int)(a[0] - '0') > (int)(b[0] - '0');
}
int changeNum(string s){//将字符串转换为数字
  int num = 0;
  for(int i = 0; s[i] != '\0'; i++){
      num = num * 10 + s[i] - '0';
  }
  return num;
}
int combine(int a, int b){//a + b组合：a在前 b在后 
  int sum = a;
  int x[30];    //储存b数中的各个位的数
  int i = 0; 
  while(b != 0){
      x[i] =  b % 10;
      b /= 10;
      i++;
  }
  for(int j = i - 1; j >= 0; j){//x中的储存顺序：个位 十位 百位 ...
      sum = sum * 10 + x[j];
  }
  return sum;
}
bool compare(int a, int b){//假设 : ab > ba 
  if(combine(a,b) > combine(b, a)){
      return true;
  }else{
      return false;
  }
}
int main() {
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
      cin >> str[i];
  } 
  sort(str, str + n, judge);
  for(int i = 0; i < n - 1; i++){
      if(str[i][0] == str[i + 1][0] ){
          int a = changeNum(str[i]);
          int b = changeNum(str[i + 1]);
          if(!compare(a, b)){
              swap(str[i], str[i + 1]);
          }
      }
  }
  for(int i = 0; i < n; i++){
      cout << str[i];
  }
  return 0; 
}
  • 看了别人的题解：
    • 1.对C++语言的熟练度还不够，字符串可以直接相加拼起来，直接用"<"、">"、"="等符号按字典序排序
    • 2.这个题本质就是“谁排在谁前面更大”，直接就能解决。
      #include<iostream>
#include<algorithm>
using namespace std;
string str[22];
bool cmp(string a, string b){
  return a + b > b + a;
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++){
  cin >> str[i];
} 
sort(str, str + n, cmp);
for(int i = 0; i < n; i++){
  cout << str[i];
}
return 0; 
}