Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.89
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
#1

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

23.02.2010, 16:58. Просмотров 6233. Ответов 8
Метки нет (Все метки)

Ограничение времени: 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 интов и пару дополнительный переменный, на линковку жлементов сета не хватает памяти, помогите пожалуйста..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.02.2010, 16:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Медиана последовательности (C++):

Медиана массива - C++
Всем привет! Помогите кто чем может с задачей а то сдавать через пару дней, незнаю что делать:( Сама задача-- В массиве,...

Медиана вхождений в документы - C++
Написать программу, которая в качестве аргументов командной строки принимает заданное слово (первый аргумент) и имена текстовых файлов...

Найти, сколько членов первой последовательности совпадает с членами второй последовательности - C++
Даны две последовательности целых чисел а1 и а2 an и b1 и b2 bn. Все члены последовательностей различные числа. Найти, сколько членов...

В последовательности Фибоначчи найти индекс члена последовательности, удовлетворяющего условию - C++
помогите не могу найти ошибку вводится число A,найти номер К такого числа Фибоначчи ,что Xк-1&lt;=A&lt;Xк. #include &lt;iostream&gt; ...

В последовательности найти числа, которые близки к числам другой последовательности - C++
даны две последовательности чисел A = {a1, a2,…, an}, B = {b1, b2, …, bn},напечатать те и только те числа aj из последовательности A, для...

Построить элементы в убывающей последовательности и вывести первоначальные индексы последовательности - C++
Здравствуйте, уважаемые форумчане!! Помогите разобраться с лабораторной работой Задача -&gt; Построить элементы в убывающей...

8
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
24.02.2010, 07:44 #2
там подойдёт массив unsigned char
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
24.02.2010, 08:13  [ТС] #3
он меньше занимает? числа в диапазоне -(2^31)-1...-(2^31)-1
0
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
24.02.2010, 08:41 #4
значит другой алгоритм
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
24.02.2010, 18:04  [ТС] #5
что быстрей сет или приорити квив ??
0
accept
4825 / 3246 / 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. вывести медиану
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.02.2010, 15:01  [ТС] #7
ага, сортировка это O(n*logn), это 250,000*18 = 4,500,000 это в 0,5 сек не влазит..
0
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
27.02.2010, 05:12 #8
можно посчитать сколько каждое число встречается
сколько всего разных чисел
потом представить полученный ряд
и медиану как бы выровнять в нём
1
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
28.02.2010, 05:43 #9
представил для миллиардных 250000 разных чисел - не подходит алгоритм
но нашёл другой

устанавливаешь границы на наименьший элемент и наибольший элемент
потом одновременно сужаешь границы, пока меньшая меньше большей
остаётся медиана
0
28.02.2010, 05:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.02.2010, 05:43
Привет! Вот еще темы с ответами:

Вывод последовательности, определяющий, являются ли простыми/совершенными соответствующие элементы введённой последовательности - C++
Никак не приходит в голову, как составить алгоритм, реализующий проверку на то, является ли число простым и является ли совершенным. Если...

Массив. Найти, сколько членов первой последовательности совпадает с членами второй последовательности - C++
Всем привет! Нужна помощь в решении задачки. Вот её условие: Даны две последовательности целых чисел а1, а2,..., аn и b1, b2,...,...

Найти сумму элементов последовательности, начиная от первого отрицательного элемента и до конца последовательности. - C++
Помогите написать простенькую программку :( Найти сумму элементов последовательности x1, x2, …, xn (x&lt;=30), начиная от первого...

Даны две последовательности.Верно ли, что все числа второй последовательности входят в первую. - C++
Даны две последовательности {a}_{1},{a}_{2},...,{a}_{n} и {b}_{1},{b}_{2},...,{b}_{m} (m&lt;n). В каждой из них числа различны. Верно ли,...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru