c++ - 数组 : Largest possible number

Question

给定一个元素数组，找到最大可能的数字通过使用数组的元素形成。
例如:10 9
答:910
2 3 5 78
答:78532
100 9
答:9100

我知道这个问题有一个使用自定义字符串比较器的解决方案，但我不明白它是如何工作的。

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>

    using namespace std;


    bool compare ( string a, string b )  
    {  
            return atoi( (a+b).c_str() ) < atoi((b+a).c_str() );  
    }

    int main()  
    {  
            vector<string> vs;  
            string s;  
            while ( cin >> s ) {  
                    vs.push_back(s);  
            }  
            sort( vs.begin(), vs.end(), compare );  
            for ( int i = vs.size()-1; i >= 0; i-- ) {  
                    cout << vs[i];  
            }  
    }   

谁能提出一个算法来解决这个问题？对上述比较器的解释将不胜感激。谢谢

Answer 1

事实上，如果我们有两个字符串 S 和 T，我们通常会按字典倒序将它们连接起来，以使最大的数字出现在前面。但是，当其中一个字符串是另一个字符串的前缀时，这种方法并不完美。
令T = SA，即S是T的前缀。我们有两种连接选择:SSA 和 SAS。显然，我们的选择将取决于哪个数字更大:AS 或 SA。以下是满足此算法的代码修改:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;


bool compare ( string a, string b )  
{  
        int i, j;
        for( i = 0; i < a.size() && i < b.size(); ++i )
               if( a[ i ] != b[ i ] )
                     break;
        if( i < a.size() && i < b.size() ) //  if digit mismatch happened
               return a[ i ] < b[ i ];
        if( i == a.size() )                // a is a prefix for b
        {
               string suffix = b.substr( i );
               return a + suffix < suffix + a;
        }
        else                               // b is a prefix for a
        {
               string suffix = a.substr( i );
               return suffix + b < b + suffix;
        }
}

int main()  
{  
        vector<string> vs;  
        string s;  
        while ( cin >> s ) {  
                vs.push_back(s);  
        }  
        sort( vs.begin(), vs.end(), compare );  
        for ( int i = vs.size()-1; i >= 0; i-- ) {  
                cout << vs[i];  
        }  
}