來自給定數字塊的最大可能數C++

Question

對於給定數量的數字塊（塊數大於2且小於1000），打印最大可能數。

這裏有一個小例子：

輸入：

5 // Number of blocks of digits 

9 // first block 

98 // second 

90 // third 

5 // fourth 

9 // fifth 

輸出：

9998905 // The biggest possible number 

我的工作在這個問題上一點點，我已經找到了算法，它似乎喜歡它的工作的任何組合，但我有問題，用C++編寫代碼

這裏的算法：

首先我輸入他們作爲一個字符串，因爲我可以muc更容易使用特定的數字。 然後我將每個數字的第一個數字與每個數字的第一個數字進行比較。並按升序排列。 如果第一個數字相同，我會檢查第二個數字，以此類推到最後一個數字。 如果兩個數字有不同的長度，而小的是另一個的子串，那麼我會在較大的數字前面排序。

正如我之前所說，這個算法工作正常，但我需要的代碼，因爲我有問題。

這是我的工作，直到如今

#include <iostream> 
#include <string>> 
using namespace std; 
int main() 
{ 
    int nums, maxsl = 0; 
    cin >> nums; 
    string s[nums]; 
    for(int i = 0; i<nums; i++) 
    { 
     cin >> s[i]; 
     if(s[i].length() > maxsl) 
     { 
      maxsl = s[i].length(); 
     } 
    } 
    for(int i = 0; i<nums; i++) 
    { 
     for(int j = 0; j<nums; j++) 
     { 
      for(int k = 0; k<=maxsl; k++) 
      { 
       if(k<=s[i].length() && k<= s[j].length()) 
       { 
        if(s[i][k]>s[j][k]) 
        { 
         string t = s[i]; 
         s[i] = s[j]; 
         s[j] = t; 
        } 
       } 
       else 
       { 
        if(s[i].length() > s[j].length()) 
        { 
         string t = s[i]; 
         s[i] = s[j]; 
         s[j] = t; 
        } 
       } 

      } 
     } 

    } 

    for(int i = 0; i<nums; i++) 
    { 
     cout << s[i]; 
    } 
} 

但是這些代碼只打印它們按升序排列，而不是最大數量更多鈔票。 這裏是前面例子的輸出：9890995

Answer 1

你的算法不正確：你不能按照字典順序對塊進行排序，因爲它們長度不同。 9應該被認爲大於98，但是它在詞典上更小（與「汽車」在字典中的「卡通」之前排序相同）。

編輯：

如asaelr建議在一個評論，來比較的位數的兩個塊的一種方式是膠合在一起兩種方式（A+B和B+A; +裝置級聯），並且檢查與順序產生數量更多。如果A+B大於B+A，請保持當前訂單;否則，請切換號碼。

將比較這樣的數字的函數傳遞給std::sort時，會生成正確的結果。

下面是這個簡單算法的實現：

#include <string> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <iostream> 
using namespace std; 

bool ahead_of(string left, string right) { 
    // Try gluing the blocks both ways, and return true or false 
    // based on which order produced a bigger result. 
    string a = left+right; 
    string b = right+left; 
    return a > b; 
} 

int main() { 
    int n; 
    // Read the number of items 
    cin >> n; 
    vector<string> items; 
    // Read the items themselves 
    for (int i = 0 ; i != n ; i++) { 
     string s; 
     cin >> s; 
     items.push_back(s); 
    } 
    // Sort using the custom comparer 
    sort(items.begin(), items.end(), ahead_of); 
    // Copy the result to the output 
    ostream_iterator<string> out_it (cout, ""); 
    copy(items.begin(), items.end(), out_it); 
    return 0; 
}