数组:最大可能的数字

Question

给定一个元素数组,找到可以通过使用数组元素形成的最大可能数.
例如:10 9
ans:910
2 3 5 78
ans:78532
100 9
ans: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];  
        }  
}