Какое число не содержится в массиве

21.12.2016, 10:04

Сообщение от jackera

Подскажите в какую сторону думать . Мне кажется что нужно как-то сравнивать числа по 1 разряду и сортировать по возрастанию?

Нужно сравнивать строковые представления чисел лексикографически и сортировать по убыванию, исключая случай, когда одна строка является префиксом другой, в этом случае результат может быть неверным.
Действительно, если мы сравниваем строки П и ПХ, то лексикографически префикс всегда меньше, и мы получим результирующую строку ПХП. Очевидно, что она больше строки ППХ только в том случае, если хвост Х лексикографически больше префикса П.
Например, для чисел 10 и 100 лексикографическое сравнение даст результат 10010, а верный ответ – 10100.

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

//Составить из массива чисел наибольшее возможное число – C++
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::string T_str;
typedef unsigned long long T_int;
typedef std::vector < T_int > T_numbers;
typedef std::vector < T_str > T_strings;
///////////////////////////////////////////////////////////////////////////////
T_str make_max_num_str( T_numbers const & numbers )
{
T_strings strings;

for( auto num : numbers )
{
strings.emplace_back (
std::to_string( num )
);
}//for

std::sort
(
strings.begin (),
strings.end (),

[] (
auto const & L,
auto const & R
)
{
return R + R
< L + L;
}
);

T_str res_str;

for( auto const & str : strings )
{
res_str += str;
}

return res_str;
}
///////////////////////////////////////////////////////////////////////////////
int main()
{
T_int n{};
std::cout << “n = “;
std::cin >> n;

T_numbers numbers(n);

for( T_int i{}; i < n; ++i )
{
std::cout << “num_”
<< i + 1
<< “t= “;

std::cin >> numbers[i];
}//for

std::cout << make_max_num_str( numbers )
<< std::endl;
}