指定された桁のブロックから最大可能数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++でコードを書く際に問題があります

アルゴリズムは次のとおりです。

最初に文字列として入力します。なぜなら、特定の数字を簡単に使用できるからです。 次に、すべての数字の最初の数字と、すべての数字の最初の数字を比較しています。昇順に並べます。 最初の桁が同じ場合は、2桁目をチェックしています。最後の桁も同様です。 2つの数字の長さが異なっていて、小さい方が小さい場合は、大きい方の数字の前に小さい数字を並べます。

私が以前に言ったように、このアルゴリズムは正常に動作しますが、問題があるのでコードが必要です。

#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より大きいと見なされるべきであるが、それは辞典的にはより小さい（辞書の中の "漫画"より先に "車"の並べ替えと同じ理由で）。

EDIT：

asaelrは数字の二つのブロックを比較する1つの方法は一緒に両方の方法、それらを接着され、コメントで示唆されるように（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; 
}