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++ 编写代码时遇到问题

这是算法：

首先，我将它们作为字符串输入，因为我可以更轻松地使用特定数字。然后我将每个数字的第一个数字与每个数字的第一个数字进行比较。并按升序排列它们。如果第一个数字相同，我正在检查第二个数字，依此类推到最后一个数字。如果两个数字的长度不同，并且较小的数字是另一个数字的子字符串，我将较小的数字放在较大的数字前面。

正如我之前所说，这个算法工作正常，但我需要代码，因为我遇到了问题。

这是我到目前为止的工作：

#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 在评论中所建议的那样，比较两个数字块的一种方法是将它们以两种方式粘合在一起（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 回答