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

Медиана последовательности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.89
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
23.02.2010, 16:58     Медиана последовательности #1
Ограничение времени: 1.0 секунды
Ограничение памяти: 1 МБ


Пусть задана последовательность из N целых неотрицательных чисел. Медианой такой последовательности в случае нечетного N называется элемент, который будет равноудален от концов последовательности, если ее отсортировать по возрастанию или убыванию (нетрудно сообразить, что этот элемент имеет номер (N+1)/2 в отсортированной последовательности, если номера считать с единицы). В случае четного N медианой называется среднее арифметическое двух элементов, которые окажутся на местах N/2 и (N/2)+1, если последовательность отсортировать. Однако исходная последовательность не обязана быть отсортированной.
Напишите программу, которая по заданной входной последовательности вычисляет ее медиану.

Исходные данные
В первой строке входа содержится число N — длина последовательности. Во второй и последующих строках расположены сами элементы последовательности, по одному в каждой строке. Длина последовательности — целое число от единицы до 250 000. Каждый элемент последовательности — целое число от 0 до (231−1) включительно.

Результат
Программа должна выдать значение медианы с точностью до одного десятичного знака.

Пример
исходные данные
4
3
6
4
5
результат
4.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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
#define FOR(i,a,b) for (int i = (a), _n(b); i < _n; ++i)
#define ALL(a) a.begin(), a.end()
 
int main ()
{
    //freopen("test.txt","r",stdin);
    int n;
    scanf("%d", &n);
    multiset <int> L, R;
    
    int d = 1, val;
    FOR(i,0,n)
    {
        scanf("%d", &val);
        if (d)  L.insert(val);
        else R.insert(val);
        d = !d;
        
        while (1 && i)
        {
            if (*L.rbegin() <= *R.begin()) break;
            L.insert(*R.begin());
            R.erase( find(ALL(R), *R.begin()) );
            R.insert(*L.rbegin());
            L.erase( find(ALL(L), *L.rbegin()) );
        }
    }
 
    double res =  *(L.rbegin());
    if (n&1) printf("%d\n", int(res) );
    else
    {
        res += *(R.begin());
        res /= 2;
        printf("%.1f\n", res);
    }
 
    return 0;
}
Он не прошел по памяти, т.к. ее ровно на 250 000 интов и пару дополнительный переменный, на линковку жлементов сета не хватает памяти, помогите пожалуйста..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.02.2010, 16:58     Медиана последовательности
Посмотрите здесь:

C++ Найти сумму элементов последовательности, начиная от первого отрицательного элемента и до конца последовательности.
C++ Медиана массива
Вывод последовательности, определяющий, являются ли простыми/совершенными соответствующие элементы введённой последовательности C++
Даны две последовательности.Верно ли, что все числа второй последовательности входят в первую. C++
C++ Каждое простое число последовательности увеличить в два раза, посчитать количество простых чисел в исходной последовательности
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
24.02.2010, 07:44     Медиана последовательности #2
там подойдёт массив unsigned char
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
24.02.2010, 08:13  [ТС]     Медиана последовательности #3
он меньше занимает? числа в диапазоне -(2^31)-1...-(2^31)-1
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
24.02.2010, 08:41     Медиана последовательности #4
значит другой алгоритм
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
24.02.2010, 18:04  [ТС]     Медиана последовательности #5
что быстрей сет или приорити квив ??
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
26.02.2010, 02:43     Медиана последовательности #6
мне показалось, что числа займут мегабайт
алгоритм тот же

числа займут 1000000, ещё 48576 остаётся

"найти медиану чисел"
  1. ввести числа
    1. ввести количество чисел
    2. выделить память для чисел
    3. сохранить числа в памяти
  2. найти медиану
    1. отсортировать числа
    2. выбрать медиану
      1. средний элемент или среднее значение двух средних элементов
    3. сохранить медиану
  3. удалить числа
    1. освободить память
  4. вывести медиану
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
26.02.2010, 15:01  [ТС]     Медиана последовательности #7
ага, сортировка это O(n*logn), это 250,000*18 = 4,500,000 это в 0,5 сек не влазит..
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
27.02.2010, 05:12     Медиана последовательности #8
можно посчитать сколько каждое число встречается
сколько всего разных чисел
потом представить полученный ряд
и медиану как бы выровнять в нём
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.02.2010, 05:43     Медиана последовательности
Еще ссылки по теме:

Массив. Найти, сколько членов первой последовательности совпадает с членами второй последовательности C++
C++ Даны две последовательности. Верно ли, что все члены второй последовательности входят в первую?
Построить элементы в убывающей последовательности и вывести первоначальные индексы последовательности C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
28.02.2010, 05:43     Медиана последовательности #9
представил для миллиардных 250000 разных чисел - не подходит алгоритм
но нашёл другой

устанавливаешь границы на наименьший элемент и наибольший элемент
потом одновременно сужаешь границы, пока меньшая меньше большей
остаётся медиана
Yandex
Объявления
28.02.2010, 05:43     Медиана последовательности
Ответ Создать тему
Опции темы

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