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

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

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

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

13.08.2014, 19:20. Просмотров 444. Ответов 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 и вывести их сумму (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
13.08.2014, 19:56 #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
Сообщений: 726
13.08.2014, 20:31 #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
будем поддерживать бинарную кучу на максимум размером http://www.cyberforum.ru/cgi-bin/latex.cgi?L/2, где http://www.cyberforum.ru/cgi-bin/latex.cgi?L - длина текущего префикса.
итерация состоит в том, что добавляется новый элемент (InsertKey), и извлекается текущий максимум (ExtractMax). размер останется необходимым, притом извлеченный элемент является медианой текущего префикса.
zss
Модератор
Эксперт С++
6359 / 5923 / 1920
Регистрация: 18.12.2011
Сообщений: 15,227
Завершенные тесты: 1
13.08.2014, 20:48 #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 #5
zss, 1) если это запрещено правилами форума, то покадите мне это и я не буду так делать.
2)А что с ней не так?
3 - 4) может быть и верно, но тогда Вам такой вопрос: почему начали критиковать мое решение, если сами не написали(не придумали, не захотели...) свое?
zss
Модератор
Эксперт С++
6359 / 5923 / 1920
Регистрация: 18.12.2011
Сообщений: 15,227
Завершенные тесты: 1
14.08.2014, 20:24 #6
1. Ответ надо давать лаконично, не забивая его информацией не относящейся к теме.
2. 1e9 - это double константа, а не int
3. Обязанности у меня такие - следить за базаром.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
14.08.2014, 20:54 #7
zss, чем плохо так писать const int INF = 1e9? чем плохо писать const long double mul = 1?
zss
Модератор
Эксперт С++
6359 / 5923 / 1920
Регистрация: 18.12.2011
Сообщений: 15,227
Завершенные тесты: 1
14.08.2014, 21:07 #8
В первом случае при преобразовании double константы 1e9 в int
может получиться 999999999 или 1000000001 из-за ошибок округления.
А во втором - ну неужели так трудно поставить точку: double mul = 1.;
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
14.08.2014, 21:16 #9
Была тут тема недавно. У человека при присваивании результата функции std:ow( 10, 2 ) целому получалось 99 вместо 100. Не знаю, правда, как с преобразованием на стадии комплиции.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
14.08.2014, 21:35 #10
zss, никогда так не случалось
и даже больше скажу, некоторые пишут и так const long long INF64 = (long long)(1e18) и тоже все норм
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2014, 21:35
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.08.2014, 21:35
Ответ Создать тему
Опции темы

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