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-9

typedef long long ll;

using namespace std;

int n;

char str[];

char a[][];

char s2[],s3[];

int cmp(const void *a,const void *b)

{

     return strcmp((char *)b,(char *)a);

}

int main()

{

    while(scanf("%d",&n)!=EOF&&n!=)

    {

        for(int i=;i<n;i++)

            scanf("%s",a[i]);

        qsort(a,n,sizeof(a[]),cmp);

        for(int i=;i<n;i++)

        {

            for(int j=;j<n-i;j++)

            {

                strcpy(s2,a[j+]);

                strcat(s2,a[j]);

                strcpy(s3,a[j]);

                strcat(s3,a[j+]);

                if(strcmp(s2,s3)>)

                {

                    strcpy(str,a[j]);

                    strcpy(a[j],a[j+]);

                    strcpy(a[j+],str);

                    //printf("%s %s\n",a[j],a[j+1]);

                }

            }

        }

        for(int i=;i<n;i++)

        {

            printf("%s",a[i]);

        }

        cout<<endl;

    }

    return ;

}

巴特西

UVA10905: Children's Game（排序）

最新文章

热门文章