Сортировка по сумме цифр - Сириус

@Eisenstein · Регистрация: 28.06.2021

Студворк — интернет-сервис помощи студентам

Напишите программу, которая сортирует натуральные числа в массиве по убыванию суммы цифр десятичной записи числа. При равенстве сумм цифр числа должны сохранить исходный порядок.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N чисел — элементы массива. Гарантируется, что 0 <N≤ 1000 .

Выходные данные
Программа должна вывести в одной строке элементы массива, отсортированного в порядке убывания суммы цифр десятичной записи числа, разделив их пробелами.

Примеры
Ввод
6
9 21 32 55 81 11
Вывод
55 9 81 32 21 11

На проверке пишет, что программа выдаёт неверный ответ. Не понимаю, что не так, помогите, пожалуйста

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool cmp(int x, int y)
{
    return x % 10 + x / 10
    < y % 10 + y / 10;
    
}
 
int main()
{ 
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.rbegin(), a.rend(), cmp);
    for (int i = 0; i < a.size(); ++i)
        cout << a[i] << " ";
    return 0;
}

@alexu_007 · 08.07.2021, 22:36

Массив массивов это круто.

А я бы создал структуру, в которой будет 2 элемента - само число и сумма его цифр. А потом отсортировал массив структур по сумме цифр.

Если есть ограничения по памяти, можно не создавать дополнительных массивов, а каждый раз считать сумму цифр для числа "на лету" и сортировать по этой сумме. Это будет медленнее и больше бесполезных расчётов.

Только неинтересно решать такую примитивную задачу.

@Obivashka · 14.03.2023, 21:54

Вот код несколько попроще, чем данный ранее. Надеюсь будет попонятнее.
P.S. У меня тоже возникала такая проблема: несмотря на то, что ответ выводился правильный, тестировщик писал, что ответ неверный. Насколько я понял, проблема заключается в том, что от нас хотят использования именно функции stable_sort, а не sort.

C++ (Qt)
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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int sum_chi(int  a)        // Программа для поиска суммы цифр в числе. Число может быть больше 100
{
    int  suma = 0;        // Переменная, в которую записывается сумма цифр
    int  i = 1;
    while (a/i != 0) {               // Проверяем не больше ли наше число чем 10^n, где n принадлежит целым неотрицательным
        suma += (a/i)%10;       // С помощью кода в этой строке можно извлечь n-ный разряд из числа a : razrad = (a/10**n)%10
        i*=10;                          // Изменяем переменную для поиска следующего разряда
    }
    return suma;
}
 
bool sumcif(int  a, int  b)       // Ключ сортировки
{ 
    return sum_chi(a)<sum_chi(b);         // Сравнения суммы цифр в числе
}
 
int main()
{
    int  n;
    cin >> n;
    vector<int > sp(n);
    for(int  i = 0; i < n; ++i) {
        cin >> sp[i];                 
    }
    stable_sort(sp.rbegin(), sp.rend(), sumcif);
    for (int  i : sp) {
        cout << i << " ";
    }
}

@Compoter25120 · 24.05.2023, 14:22

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
 
#include <iostream>
using namespace std;
unsigned DigitSum( unsigned x ) {
   unsigned sum = 0;
   while ( x != 0 ) {
       sum += x % 10;
       x /= 10;
   }
   return sum;
}
bool Comparison( const unsigned a, const unsigned b ) {
   return DigitSum( a ) < DigitSum( b );
}
void InsertionSort( unsigned long *arr, size_t size, bool (*compareFunc)( const unsigned, const unsigned ) ) {
   for ( size_t i = 1; i < size; ++i )
       for ( size_t j = i; j > 0 && Comparison( arr[ j - 1 ], arr[ j ] ); --j )
           swap( arr[ j - 1 ], arr[ j ] );
}
int main() {
   const size_t maxCount = 10000;
   unsigned long* arr = new unsigned long[ maxCount ];
   size_t count = 0;
   cin >> count;
   for ( size_t i = 0; i < count; ++i ) {
       cin >> arr[ i ];
   }
   InsertionSort( arr, count, Comparison );
   for ( size_t i = 0; i < count; ++i )
       cout << arr[ i ] << " ";
   delete[] arr;
   return 0;
}

@Pythonist213 · 20.06.2023, 12:15

Да, да, прошло 2 года, не скажешь, пожалуйста, так в чем был подвох??

@AK-rasava · 01.08.2024, 19:51

Проблема в том, что stable_sort сохраняет порядок при сортировке. Странно только, что в Сириус это не сказали -_-

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
unsigned summ_digits(int x)
{
    unsigned summ = 0;
    while (x)
    {
        summ += x % 10;
        x = x / 10;
    }
    return summ;
}
 
bool mp(int x, int y)
{
    return summ_digits(x) < summ_digits(y);
}
 
int main()
{
    int n;
    cin >> n;
    vector <int> num(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> num[i];
    }
    
    stable_sort(num.rbegin(), num.rend(), mp);
    
    for (int i = 0; i < n; ++i)
    {
        cout << num[i] << " ";
    }
    
    return 0;
}

@SmallEvil · 01.08.2024, 21:18

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
#include <iostream>
#include <map>
#include <deque>
#include <functional>
 
int main(){
   using list_t = std::deque<unsigned>;
   using voc_t  = std::map<std::uint8_t, list_t, std::greater<>>;
   
   auto digits_sum = [](unsigned num){
      unsigned sum = 0;
      while(num)
         sum += num%10, num /= 10;
      return sum;
   };
   
   unsigned n, num;
   voc_t voc;
   
   std::cin >> n;
   while(n--){
      std::cin >> num;
      voc[digits_sum(num)].push_back(num);
   }
   
   for(const auto &p : voc){
      for(const auto &num : p.second)
         std::cout << num << ' ';
   }
   std::cout << std::endl;
}

Новые блоги и статьи Все статьи Все блоги /
[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .

@alexu_007 736 / 703 / 110 Регистрация: 29.05.2015 Сообщений: 4,293
	08.07.2021, 22:36
	Массив массивов это круто. А я бы создал структуру, в которой будет 2 элемента - само число и сумма его цифр. А потом отсортировал массив структур по сумме цифр. Если есть ограничения по памяти, можно не создавать дополнительных массивов, а каждый раз считать сумму цифр для числа "на лету" и сортировать по этой сумме. Это будет медленнее и больше бесполезных расчётов. Только неинтересно решать такую примитивную задачу. 2

@Pythonist213 1 / 1 / 0 Регистрация: 29.10.2021 Сообщений: 8
	20.06.2023, 12:15
	Да, да, прошло 2 года, не скажешь, пожалуйста, так в чем был подвох?? 0