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

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

Войти
Регистрация
Восстановить пароль
 
MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
#1

Найти медианы на всех префиксах последовательности X длины n и вывести их сумму - C++

13.08.2014, 19:20. Просмотров 439. Ответов 9
Метки нет (Все метки)

В этой задаче необходимо найти медианы на всех префиксах последовательности X длины n и вывести их сумму.

Медианой последовательности из нечетного (k = 2 ⋅ l + 1) количества элементов будем называть элемент, который стоял бы на (l + 1)-ом месте, если эту последовательность отсортировать. Медианой последовательности из четного (k = 2 ⋅ l) количества элементов будем называть элемент, который стоял бы на l-ом месте, если эту последовательность отсортировать.


Помогите пожалуйста решить или подскажите при чем тут бинарная куча....
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.08.2014, 19:20     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму
Посмотрите здесь:

Найти количество и сумму всех членов последовательности (используя do...while) - C++
Дана последовательность чисел a1, a2, a3, .... Количество элементов в последовательности заранее неизвестно. Надо написать программу с...

Найти сумму всех элементов последовательности, больших заданного числа b - C++
Здравствуйте помогите пожалуйста написать код!Заранее спасибо)) Дана последовательность a1, a2, ..., an вещественных чисел. Найти сумму...

Необходимо найти сумму всех чисел в последовательности Фибоначчи, не превосходящих введенного числа n - C++
Последовательность Фибоначчи формируется следующим образом: первый и второй члены последовательности равны 1, а каждый следующий равен...

Найти сумму всех идущих подряд нечётных, находящихся в начале заданной последовательности - C++
Как реализовать данный алгоритм?

Найти сумму всех младших разрядов для каждого элемента заданной последовательности - C++
Помогите пожалуйста решить задачу, есть решение но не правильно решает, вроде как можно через for сделать, но что то меня тупит. Заранее...

Найти сумму всех элементов последовательности, завершающейся нулём (для решения использовать цикл while) - C++
Определите сумму всех элементов последовательности, завершающейся числом 0. Формат входных данных Вводится последовательность целых...

В заданной последовательности найти сумму всех целых чисел кратных 5 (для решения задачи использовать while) - C++
Введена последовательность n, найти сумму всех целых чисел этой последовательности кратных 5

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
13.08.2014, 19:56     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #2
так проверь:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#pragma comment(linker, "/STACK:167177216")
 
#include <stdio.h>
#include <stack>
#include <math.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string.h>
#include <string>
#include <memory.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <time.h>
#include <cassert>
#include <cstring>
//#include <unordered_set>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
 
const int INF = 1e9;
const ld eps = 1e-9;
const li MOD = (li)(INF + 7);
const li INF64 = (li)(INF) * (li)(INF);
 
const int ddx[] = {-1, 1, 1, -1};
const int ddy[] = {1, 1, -1, -1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dxh[] = {-1, -1, -1, 1, 1, 1, 1, -1};
const int dyh[] = {1, -1, -1, -1, -1, 1, 1, 1};
const string dirs[] = {"RIGHT", "UP", "LEFT", "DOWN"};
 
bool in(int i, int j, int n, int m)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
int a[111111];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("errors.txt", "w", stderr);
    //ios_base::sync_with_stdio(false);
    multiset<int> small, big;
    int sz1 = 0, sz2 = 0;
 
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
 
    for(int i = 1; i <= n; i++)
    {
        if(i == 1)
            small.insert(a[i]), sz1++;
        else
        {
            int mx_small = *small.rbegin();
            if(a[i] <= mx_small)
                small.insert(a[i]), sz1++;
            else
                big.insert(a[i]), sz2++;
        }
 
        int cnt = i;
        int SZ1 = (cnt + 1) / 2;
        int SZ2 = cnt - SZ1;
 
        while(sz1 > SZ1)
        {
            multiset<int>::iterator it = small.end();
            it--;
            int val = *it;
            big.insert(val);
            small.erase(it);
            sz1--;
            sz2++;
        }
 
        while(sz1 < SZ1)
        {
            multiset<int>::iterator it = big.begin();
            int val = *it;
            small.insert(val);
            big.erase(it);
            sz1++;
            sz2--;
        }
 
        assert(sz1 - sz2 <= 1);
 
        printf("answer for prefix %d == %d\n", i, *small.rbegin());
    }
    return 0;
}
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
13.08.2014, 20:31     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
будем поддерживать бинарную кучу на максимум размером http://www.cyberforum.ru/cgi-bin/latex.cgi?L/2, где http://www.cyberforum.ru/cgi-bin/latex.cgi?L - длина текущего префикса.
итерация состоит в том, что добавляется новый элемент (InsertKey), и извлекается текущий максимум (ExtractMax). размер останется необходимым, притом извлеченный элемент является медианой текущего префикса.
zss
Модератор
Эксперт С++
6321 / 5905 / 1913
Регистрация: 18.12.2011
Сообщений: 15,181
Завершенные тесты: 1
13.08.2014, 20:48     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #4
SlavaSSU,
1. Почему не следите за инклюдами?
Для Вашего примера нужны всего 3 (iostream, set и cassert).
Понимаю, что Вам лень каждый раз определять это,
но уж если приводите пример на форуме, то будьте добры убрать мусор!
2. Как целочисленной константе можно присвоить 1e9 (34 строка)?
3. Если используете iostream, то с какой стати scanf (66 и 68 строки)?
4. Злоупотребляете глобальными переменными. Кстати, я вообще не вижу причины для этого,
они нигде, кроме main не используются.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
13.08.2014, 22:37     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #5
zss, 1) если это запрещено правилами форума, то покадите мне это и я не буду так делать.
2)А что с ней не так?
3 - 4) может быть и верно, но тогда Вам такой вопрос: почему начали критиковать мое решение, если сами не написали(не придумали, не захотели...) свое?
zss
Модератор
Эксперт С++
6321 / 5905 / 1913
Регистрация: 18.12.2011
Сообщений: 15,181
Завершенные тесты: 1
14.08.2014, 20:24     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #6
1. Ответ надо давать лаконично, не забивая его информацией не относящейся к теме.
2. 1e9 - это double константа, а не int
3. Обязанности у меня такие - следить за базаром.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
14.08.2014, 20:54     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #7
zss, чем плохо так писать const int INF = 1e9? чем плохо писать const long double mul = 1?
zss
Модератор
Эксперт С++
6321 / 5905 / 1913
Регистрация: 18.12.2011
Сообщений: 15,181
Завершенные тесты: 1
14.08.2014, 21:07     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #8
В первом случае при преобразовании double константы 1e9 в int
может получиться 999999999 или 1000000001 из-за ошибок округления.
А во втором - ну неужели так трудно поставить точку: double mul = 1.;
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
14.08.2014, 21:16     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #9
Была тут тема недавно. У человека при присваивании результата функции std:ow( 10, 2 ) целому получалось 99 вместо 100. Не знаю, правда, как с преобразованием на стадии комплиции.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2014, 21:35     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму
Еще ссылки по теме:

Найти и вывести сумму всех дробных чисел в строке - C++
Найти и вывести сумму всех дробных чисел в строке. Размер строки 80. Вводится пользователь, но проблема в нахождении самих дробных чисел....

Дана последовательность из N вещественных чисел. Первое число в последовательности нечетное. Найти сумму всех идущих подряд в начале последовательност - C++
Дана последовательность из N вещественных чисел. Первое число в последовательности нечетное. Найти сумму всех идущих подряд в начале...

Даны длины треугольника ABC. Определить его медианы - C++
Даны длины сторон А,В,С треугольника. Определите его медианы. Длинна медианы проведенной на сторону А вычесляется по формуле...

Даны длины сторон А, В, С некоторого треугольника. Определить его медианы. - C++
Надо написать программу с функциями, перегрузку и шаблон к ней. вот задание: &quot;Даны длины сторон А, В, С некоторого треугольника....

Вывести массив содержащий длины всех серий исходного массива - C++
Снова здравствуйте! Есть задача: &quot;Дан целочисленный массив размера N. Назовем серией группу подряд идущих одинаковых элементов, а длиной...


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

Или воспользуйтесь поиском по форуму:
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
14.08.2014, 21:35     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #10
zss, никогда так не случалось
и даже больше скажу, некоторые пишут и так const long long INF64 = (long long)(1e18) и тоже все норм
Yandex
Объявления
14.08.2014, 21:35     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму
Ответ Создать тему
Опции темы

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