Сортировка массива - олимпиадная задача

@snyp · Регистрация: 11.06.2013

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

Помогите, пожалуйста, решить такую задачу:

Так как Т.В.С., М.И.М. и Г.Д.М. живут далеко от школы, то каждый день они вот
уже много лет как минимум два раза в день ездят на автобусах. В связи с этим у них
выработалась привычка составлять с помощью знаков арифметических действий и скобок
число 100 из номера билета. После того, как каждый из них приезжает домой, он достает
из карманов билеты, пишет на каждом из них текущую дату и складывает в шкаф. Их
родителям такое хранение билетов не нравится(зачем хранить мусор?), поэтому они
регулярно заставляют их выкидывать. Недавно один из участников первой команды
решил, перед тем, как выкинуть, отсортировать накопившиеся билеты по дате их
покупки. Но это оказалось не так легко, как казалось, потому что билетов было очень
много. Поэтому он обращается к вам за помощью.
Выходные данные:
В первой строке содержится число N – количество билетов(1<=N<=100000). Далее
записано N дат билетов, разделенных пробелами или символами перевода строки. Каждая
дата представляет собой четырехзначное число, первые две цифры которого означают
день покупки, а вторые две – ее месяц (например, 0309 – 3 сентября).
Выходные данные:
В каждой строке должны содержаться (по одному) отсортированные даты
приобретения билетов в том же формате, что и во входном файле.
Пример:
input
5 0203 0302
1512
0409 0101
output
0101
0302
0203
0409
1512

Задача из прошедшей олимпиады для школьников, дорешиваю, но никак на 100 баллов не тянет. Проверяющая система за нижеследующий код даёт 56 баллов из 100:

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
#include <iostream>
 
using namespace std;
 
int main(){
    int n, i, j, c, o;
    int w[100000];
    int a[100000];
    cin>>n;
    for (i=1; i<=n; i++)
        cin>>a[i];
    for (i=1; i<=n; i++)
        w[i] = (a[i]/100)+(a[i]%100)*100;
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j++)
            if (w[i]>w[j])
            {
                c=a[i];
                a[i]=a[j];
                a[j]=c;
                o=w[i];
                w[i]=w[j];
                w[j]=o;
            }
    for (i=1; i<=n; i++)
        if (a[i]<1000)
            cout<<0<<a[i]<<endl;
        else cout<<a[i];
    return 0;
}

Быть может, вы сможете её откорректировать? Или предложите свой вариант?

@dr.curse · 17.06.2013, 17:00

snyp, на первый взгляд проблема в сортировке она же квадратичная, поэтому при 100000 будет очень долго, могу предложить использовать другую сортировку например быструю

@Thinker · 17.06.2013, 17:21

сортировка подсчетом вам поможет. заведите прямоугольную матрицу порядка 12 на 31 и вперед. сложность алгоритма будет линейной и по времени ОЧЕНЬ быстрой.

@salam · 17.06.2013, 17:22

во-первых, как вам правильно намекнули, пузырек не пройдет. используйте std::sort(). только учитывайте, что сравнение должно происходить в данном случае нестандартно. нужно сравнивать сначала месяц, потом число.

@Thinker · 17.06.2013, 18:03

сортировка подсчетом в данном случае (кое-что подправил):

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
#include <iostream>
 
using namespace std;
 
int main(){
    int n, d, i, j, k;
    int count[12][31] = {0};
    cin >> n;
    for (i = 0; i < n; ++i)
    {
        cin >> d;
        ++count[d % 100 - 1][d / 100 - 1];
    }
    for (i = 0; i < 12; ++i)
       for (j = 0; j < 31; ++j)
         for (k = 0; k < count[i][j]; ++k)
         {
             d = (j + 1) * 100 + i + 1;
             if (d < 1000)
                cout << 0 << d << endl;
             else
                cout << d << endl;
         }
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	17.06.2013, 17:00
	snyp, на первый взгляд проблема в сортировке она же квадратичная, поэтому при 100000 будет очень долго, могу предложить использовать другую сортировку например быструю 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	17.06.2013, 17:21
	сортировка подсчетом вам поможет. заведите прямоугольную матрицу порядка 12 на 31 и вперед. сложность алгоритма будет линейной и по времени ОЧЕНЬ быстрой. 1

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	17.06.2013, 17:22
	во-первых, как вам правильно намекнули, пузырек не пройдет. используйте std::sort(). только учитывайте, что сравнение должно происходить в данном случае нестандартно. нужно сравнивать сначала месяц, потом число. 1