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

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

Восстановить пароль Регистрация
 
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
13.08.2014, 19:20     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #1
В этой задаче необходимо найти медианы на всех префиксах последовательности 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++
C++ 4. Найти сумму К членов последовательности: 3, 7, 11, 15,… Вычислить сумму членов последовательности 1, 4, 7, 10, …, не превосходящих числа К
C++ Дана последовательность из N вещественных чисел. Первое число в последовательности нечетное. Найти сумму всех идущих подряд в начале последовательност
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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
Модератор
Эксперт С++
 Аватар для zss
5947 / 5552 / 1785
Регистрация: 18.12.2011
Сообщений: 14,184
Завершенные тесты: 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
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
13.08.2014, 22:37     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #5
zss, 1) если это запрещено правилами форума, то покадите мне это и я не буду так делать.
2)А что с ней не так?
3 - 4) может быть и верно, но тогда Вам такой вопрос: почему начали критиковать мое решение, если сами не написали(не придумали, не захотели...) свое?
zss
Модератор
Эксперт С++
 Аватар для zss
5947 / 5552 / 1785
Регистрация: 18.12.2011
Сообщений: 14,184
Завершенные тесты: 1
14.08.2014, 20:24     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #6
1. Ответ надо давать лаконично, не забивая его информацией не относящейся к теме.
2. 1e9 - это double константа, а не int
3. Обязанности у меня такие - следить за базаром.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
14.08.2014, 20:54     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #7
zss, чем плохо так писать const int INF = 1e9? чем плохо писать const long double mul = 1?
zss
Модератор
Эксперт С++
 Аватар для zss
5947 / 5552 / 1785
Регистрация: 18.12.2011
Сообщений: 14,184
Завершенные тесты: 1
14.08.2014, 21:07     Найти медианы на всех префиксах последовательности X длины n и вывести их сумму #8
В первом случае при преобразовании double константы 1e9 в int
может получиться 999999999 или 1000000001 из-за ошибок округления.
А во втором - ну неужели так трудно поставить точку: double mul = 1.;
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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++
Даны длины треугольника ABC. Определить его медианы C++
Найти сумму положительных и сумму нечетных членов последовательности. Вывести ту сумму, которая по модулю меньше C++

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

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

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