7. 拼数

1 题目描述

拼数

成绩	10	开启时间	2021年09月24日 星期五 18:00
折扣	0.8	折扣时间	2021年11月15日 星期一 00:00
允许迟交	否	关闭时间	2021年11月23日 星期二 00:00

设有 n个正整数 a[1]​…a[n]​，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入描述

第一行有一个整数，表示数字个数 n （1 ≤ n ≤ 20, 1 ≤ a ≤ 10^9）。

第二行有 n个整数，表示给出的 n个整数 a[i]    

输出描述

一个正整数，表示最大的整数

接下来将由系统输出你的询问记录

当你的调用次数小于例程的2倍时，你将AC此题

预设代码

前置代码

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  #include<iostream>  
#include<string>  using namespace std;  
string s[25];  
int n;  int* SpellNum(int );  int cmp(int i, int j) {  if(i <= 0 || i > n || j <= 0 || j > n)  return -2;  return s[i] + s[j] > s[j] + s[i];  
}  int main() {  cin >> n;  for(int i = 1; i <= n; ++i)   cin >> s[i];  int* index = SpellNum(n);  for(int i = 1; i <= n; ++i)   cout << s[index[i]];  cout << endl;  return 0;  
}  /* PRESET CODE END - NEVER TOUCH CODE ABOVE */  

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 3↵ 13 312 343↵	以文本方式显示 34331213↵ 3↵	1秒	64M	0
测试用例 2	以文本方式显示 4↵ 7 13 4 246↵	以文本方式显示 7424613↵ 6↵	1秒	64M	0

2 代码

#include<iostream>  
#include<string>  using namespace std;  
string s[25];  
int n;  int* SpellNum(int );  int cmp(int i, int j) {  if(i <= 0 || i > n || j <= 0 || j > n)  return -2;  // 成立返回1，不成立返回0return s[i] + s[j] > s[j] + s[i];  
}  int main() {  freopen("file in.txt","r",stdin);cin >> n;  for(int i = 1; i <= n; ++i)   cin >> s[i];  int* index = SpellNum(n);  for(int i = 1; i <= n; ++i)   cout << s[index[i]];  cout << endl;  return 0;  
}  // 方法就是把数字做为字符串来排序，排序的比较原则是： 两个数字串A，B，如果AB < BA，则A < B
// 不让访问原数组，那就新建一个数组把原数组的下标保存下来，对原数组的下标进行操作
int *SpellNum(int n){int *index;index = (int*)malloc(sizeof(int)*(n+1)); //下标0的那一位没有使用，所以多申请一个位置	int i,j;int temp;int ans;for(i=1;i<=n;i++){index[i]=i;}for(i=1;i<n;i++){for(j=i+1;j<=n;j++){ans = cmp(index[i],index[j]);if(ans==-2){exit;}else if(ans){// 如果大于的话，不做任何操作}else{// 如果小于的话，交换位置temp = index[i];index[i]=index[j];index[j]=temp;}		}}return index;
}