Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.
Input Specification:
Each input file contains one test case. Each case gives a positive integer N (<=10000) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the smallest number in one line. Do not output leading zeros.
Sample Input:
5 32 321 3214 0229 87
Sample Output:
22932132143287
備注:思路是将字元串排序,排序的比較規則是:兩個字元串m和n,比較拼接起來的兩個數mn和nm誰更小。另外要注意一些邊界條件判斷,例如所有的輸入都為0,這時要輸出一個0為最終結果。
程式的細節點是字元串指針數組的qsort寫法,第三個參數是sizeof(char *),是以傳遞給比較函數compare的參數就是指針的指針,即char **。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int MAXSIZE = 10;
const int MAXNUM = 10005;
int compare(const void *a, const void *b)
{
char *s1 = *(char **)a;
char *s2 = *(char **)b;
char tmp1[MAXSIZE*2+1];
char tmp2[MAXSIZE*2+1];
// s1s2
strcpy(tmp1,s1);
strcat(tmp1,s2);
// s2s1
strcpy(tmp2,s2);
strcat(tmp2,s1);
return strcmp(tmp1,tmp2);
}
bool IsAllZeros(char *s)
{
for(int i=0;s[i]!='\0';i++)
{
if(s[i]!='0')
return false;
}
return true;
}
int main()
{
int n,i;
bool endofzeros = false;
char *s_list[MAXNUM];
scanf("%d",&n);
for(i=0;i<n;i++)
{
s_list[i] = new char[MAXSIZE];
scanf("%s",s_list[i]);
}
qsort(s_list,n,sizeof(char *),compare);
for(i=0;i<n;i++)
{
if(!IsAllZeros(s_list[i]))
break;
}
if(i==n)
{
printf("0");
return 0;
}
for(int j=i;j<n;j++)
{
// omit the leading zeros
if(j==i)
{
for(int k=0;s_list[j][k]!='\0';k++)
{
if(endofzeros)
printf("%c",s_list[j][k]);
else if(!endofzeros && s_list[j][k]!='0')
{
endofzeros = true;
printf("%c",s_list[j][k]);
}
}
}
else
printf("%s",s_list[j]);
}
return 0;
}