Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
snyp
4 / 4 / 4
Регистрация: 11.06.2013
Сообщений: 27
17.06.2013, 16:52     Сортировка массива - олимпиадная задача #1
Помогите, пожалуйста, решить такую задачу:

Так как Т.В.С., М.И.М. и Г.Д.М. живут далеко от школы, то каждый день они вот
уже много лет как минимум два раза в день ездят на автобусах. В связи с этим у них
выработалась привычка составлять с помощью знаков арифметических действий и скобок
число 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;
}
Быть может, вы сможете её откорректировать? Или предложите свой вариант?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2013, 16:52     Сортировка массива - олимпиадная задача
Посмотрите здесь:

Олимпиадная задача C++
Анаграммы(олимпиадная задача) C++
C++ Олимпиадная задача
Олимпиадная задача C++
Задача на дп (олимпиадная) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
17.06.2013, 17:00     Сортировка массива - олимпиадная задача #2
snyp, на первый взгляд проблема в сортировке она же квадратичная, поэтому при 100000 будет очень долго, могу предложить использовать другую сортировку например быструю
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.06.2013, 17:21     Сортировка массива - олимпиадная задача #3
сортировка подсчетом вам поможет. заведите прямоугольную матрицу порядка 12 на 31 и вперед. сложность алгоритма будет линейной и по времени ОЧЕНЬ быстрой.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
17.06.2013, 17:22     Сортировка массива - олимпиадная задача #4
во-первых, как вам правильно намекнули, пузырек не пройдет. используйте std::sort(). только учитывайте, что сравнение должно происходить в данном случае нестандартно. нужно сравнивать сначала месяц, потом число.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.06.2013, 18:03     Сортировка массива - олимпиадная задача #5
сортировка подсчетом в данном случае (кое-что подправил):
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;
}
Yandex
Объявления
17.06.2013, 18:03     Сортировка массива - олимпиадная задача
Ответ Создать тему
Опции темы

Текущее время: 16:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru