数字积木 - 编程论坛

#2

rjsp2015-12-01 14:40

程序代码：

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

int main( void )
{
    size_t n;
    cin >> n;
    std::vector<std::string> ns;
    std::copy_n( std::istream_iterator<std::string>(cin), n, std::back_inserter(ns) );
    std::sort( std::begin(ns), std::end(ns), [](const std::string& a, const std::string& b){return a+b>b+a;} );
    std::copy( std::begin(ns), std::end(ns), std::ostream_iterator<std::string>(cout,"") );
    return 0;
}

#3

Julien2015-12-02 13:00

能说一下大概思路吗

#4

Julien2015-12-02 13:36

二、数字积木(brick.pas/c/cpp)
    算法分析：
    本题每个数都比较大，所以用字符串操作。
    朴素算法是求出所有排列，求出其中能拼成的最大值，这样能拿30分左右。
    一种贪心策略是单纯地比较字符串间的大小，把大的放在前面。但很快就能发现反
例，例如：“131”>“13”，但“13113”<“13131”。那我们再考虑一下拼接后的情况，在操作时，将单纯地比较字符串大小变成比较“拼接”后的字符串大小就可以了。例如：比较131和13，因为“13113”<“13131”，所以13应该比131大，应排在131前面。
    所以只有用一个排序算法，把两个字符串的大小比较改为“拼接”后的字符串大小比
较就行了。
能分析一下吗

#5

须臾以南2015-12-02 13:50

可以的！！！！！！！

#6

须臾以南2015-12-02 13:52

用string输入字符串，直接相加两两比较，如果小于就交换两数位置。最后输出

#7

Julien2015-12-02 16:34

明白了

，谢谢