NOIP 1998 拼数(贪心)

Bertha 。 2022-05-17 09:29 169阅读 0赞

题目描述

设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。  
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213  
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

输入

每个测试文件只包含一组测试数据，每组输入数据的第一行输入一个正整数n（n≤20）。  
接下来一行输入n个正整数。

输出

对于每组输入数据，输出n个正整数联接成的最大的多位整数。

分析：要想最后的值最大，很明显我们应该把大的数字排前面，贪心就好了，即（如果b+a>a+b 则交换位置）为什么不能直接b>a，就交换位置呢？，例如 800 和 80，按照排好序后，会输出80080，但其实应该是80800，所以排序的时候要两两连接起来进行排序。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e2+7;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    string a[maxn];
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    bool cmp(string a,string b)
    {
        return a+b>b+a;
    }
    
    int main()
    {
        int n=read();
        fup(i,0,n)
            cin>>a[i];
        sort(a,a+n,cmp);
        fup(i,0,n)
           cout<<a[i];
        printf("\n");
        return 0;
    }