浙大PAT_1038：Recover the Smallest Number 解题报告

题目：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.

先贴代码，后解释。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define N 10000

struct S
{
	string data;
	int valid;
	int rank;
};

bool compare(S a, S b)
{
	return a.data < b.data;
}

int main()
{
	int n, i, j;
	S s[N];
	string tmp;
	bool flag;

	while (cin >> n)
	{
		for (i = 0; i < n; i++)
		{
			cin >> tmp;
			s[i].valid = tmp.length();

			s[i].data = "01234567";
			for (j = 0; j < 8; j++)  //把不足8为的数都循环补成8为，如32补为32323232
			{
				s[i].data[j] = tmp[j % tmp.length()];
			}
		}

		sort(s, s+n, compare);

		flag = 0;
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < s[i].valid; j++)
			{
				if (flag)
				{
					cout << s[i].data[j];
				}
				else if (s[i].data[j] != '0')
				{
					cout << s[i].data[j];
					flag = 1;
				}
			}
		}

		if (!flag)
			cout << '0';
	}

	return 0;
}
           

我的解题思路也算比较清晰易懂，利用库函数sort排序的结果，唯有32，321，3214这样的数位置不对，经观察，这三个数的正确顺序和3232，3213，3214排序后的顺序一样，故代码中把所有数都补成8为，然后再用sort排序，得到的顺序就是结果要依次输出的顺序，只是别把补充的数输出来。

注意，该题有一个陷阱，开头的0不要输出，但是如果所有的数都是0，那么最后结果要输出一个0。

后来搜索网上解法，见 Sup_Heaven的专栏解法更妙，特把代码拷贝过来以便分享。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *m,const void *n){
  char *a=(char *)m;
  char *b=(char *)n;
  char tmpa[20],tmpb[20];
  strcpy(tmpa,a);
  strcpy(tmpb,b);
  strcat(tmpa,b);
  strcat(tmpb,a);
  return strcmp(tmpa,tmpb);
}
char str[10005][10];
int main(){
  int i,j,n;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",str[i]);
  }
  qsort(str,n,10*sizeof(char),cmp);
  int flag=0;
  for(i=0;i<n;i++){
    for(j=0;str[i][j]!='';j++){
      if(flag==0&&str[i][j]=='0');
      else {flag=1;printf("%c",str[i][j]);}
    }
  }
  if(flag==0) printf("0");//如果所有段都为零，那么必须输出一个零
  printf("n");
  return 0;
} 
           

该算法的核心在与compare函数，比较两个数，如3214和87，那么比较一下321487和874214，于是把哪个数放在前面能使得到的数最小便一目了然。