Массив: максимально возможное число

Question

Учитывая массив элементов, найти максимально возможное число, которое может быть сформирован с использованием элементов массива.
например: 10 9
Ответ: 910
2 3 5 78
Ответ: 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];  
        }  
}

Answer 2

Просто отсортируйте их в лексикографическом порядке, сравнивая цифры слева направо. Таким образом, сначала появляются большие цифры, тем самым увеличивая составное число.

РЕДАКТИРОВАТЬ: Как указывает Григор, вы должны сначала перевернуть строки, отсортировать их в обратном порядке lex, затем объединить и сторнировать результат.

Answer 3

Компаратор сравнивает две строки, если комбинация a+b идет до или после b+a. Так, например, он говорит, что для ввода a=4; b=3 строка "34" на меньше , чем "43" и, следовательно, 4 должна быть раньше 3.

Числа 2 3 5 78, следовательно, будут отсортированы в 78 5 3 2 и, следовательно, результат будет 78532.

Answer 4

Вы используете оператор сравнения, чтобы найти большее из двух возможных чисел, образованных путем объединения двух чисел (строк) обоими возможными способами a+b и b+a.Поскольку вас интересует сравнение величины чисел, функция atoi() используется для преобразования строки в соответствующие числа.
Но это преобразование не требуется. Поскольку длина двух строк a+b и b+a то же самое, лексикографическое сравнение так же хорошо, как величина чисел.Преобразование требуется только в том случае, если длина сравниваемых двух строк не равна.

Answer 5

Учитывая массив целых чисел, вы можете просто выполнить несколько двоичных поисков для наибольшего числа.Каждый раз, когда вы делаете это, объединяйте число в конце вашей строки (результат) и не забудьте исключить ранее добавленные числа.