首页 > 代码库 > UVA10905: Children's Game（排序）
UVA10905: Children's Game（排序）
题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68990#problem/A
题目需求：，给n个数字，将它们重新排序得到一个最大的数字，好像给出123 456 789 拼为 789456123 最大
这题可以算是一个排序题，不过排序的规则有讲究
如果想用字典序排序，显然错了，好像999123 999 ， 按字典序排序999123在前面，得到的数字为999123999 ， 显然没有不够999999123 大
题目解析：冒泡排序，首先先按字典序排序，这样可以使冒泡排序的交换次数大大减小。
如果有两个数90 9，如果按字典序排序则90>9,此时比较strcat（“90”，“9”）与（“9”，”90“）的大小，使大的与小的位置交换。具体操作请看代码，一看就会明白什么意思的。
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <math.h>#include <queue>#define eps 1e-9typedef long long ll;using namespace std;int n;char str[101];char a[60][101];char s2[202],s3[202];int cmp(const void *a,const void *b){ return strcmp((char *)b,(char *)a);}int main(){ while(scanf("%d",&n)!=EOF&&n!=0) { for(int i=0;i<n;i++) scanf("%s",a[i]); qsort(a,n,sizeof(a[0]),cmp); for(int i=1;i<n;i++) { for(int j=0;j<n-i;j++) { strcpy(s2,a[j+1]); strcat(s2,a[j]); strcpy(s3,a[j]); strcat(s3,a[j+1]); if(strcmp(s2,s3)>0) { strcpy(str,a[j]); strcpy(a[j],a[j+1]); strcpy(a[j+1],str); //printf("%s %s\n",a[j],a[j+1]); } } } for(int i=0;i<n;i++) { printf("%s",a[i]); } cout<<endl; } return 0;}
UVA10905: Children's Game（排序）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。