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 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
| 以文本方式显示
| 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;
}