3

与えられた数字のブロック数 (ブロック数が 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

4

1 に答える 1

2

あなたのアルゴリズムは正しくありません。ブロックの長さが異なるため、ブロックを辞書順にソートすることはできません。9 は 98 より大きいと考えるべきですが、辞書的には小さいです (辞書で "car" が "cartoon" より前にソートされるのと同じ理由で)。

編集 ：

asaelr がコメントで示唆したように、2 つの数字のブロックを比較する 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;
}
于 2012-05-01T00:18:27.817 に答える