IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

> Структуры, heap, C++
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Передо мной стоит следующая задача:

Есть (N<10^5) чисел, на каждом шаге алгоритма нужно находить 2 минимальных числа и заменять их на их сумму. Так делается до тех пор, пока не останется одно число. Сделать то я сделал, вот только работает это долго.

Знаю, что есть такая структура данных как куча, которая выдает минимальный элемент за O(1) и добавляет за O(log N). Но как это реализовывать не знаю, не нашел. А то, что находил, было совсем не понятно... возможно потому, что никогда не работал со структурами.

Может это можно реализовать на простом массиве?

Помогите, кто может. smile.gif

P.S.
Вот как я делал:


#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
out.setf(ios::fixed);
out.precision(2);
double sum=0,z;
int n,i,j,d=0;
vector <int> v;
in>>n;
for(i=0;i<n;i++)
{
in>>j;
v.push_back(j);
d++;
}
while (d>1)
{
sort(v.begin(),v.end());
z=v[0]+v[1];
sum+=z/100*5; //5% процентов от полученной суммы двух этих минимальных чисел
v.push_back(z);
v.erase(v.begin(),v.begin()+2);
d--;
}
out<<sum;
return 0;
}


Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
first_day   Структуры, heap   2.05.2008 20:41
volvo   Можно посмотреть, как именно ты реализовал, и озву…   2.05.2008 21:14
first_day   что значит "долго", и насколько быстрее…   2.05.2008 21:29
klem4   немного не то написал, через час покажу на примере…   2.05.2008 21:23
volvo   Быстрее не быстрее, но 10-кратное ускорение на тво…   2.05.2008 22:00
first_day   Ну общий принцип вроде как да... Т.е. находим 2 ми…   2.05.2008 22:15
volvo   Как видно, не совсем понятно :) У тебя огромное ко…   2.05.2008 22:21
first_day   Знать бы что такое multiset... :unsure:   2.05.2008 22:26
klem4   интересное дело :) Вот смотри: http://www.cplusplu…   2.05.2008 22:44
volvo   По-моему я уже давал тебе ссылку на этот сайт: std…   2.05.2008 22:44
first_day   интересное дело :) Вот смотри: http://www.cpluspl…   2.05.2008 22:55
volvo   Запросто, меняем функцию сравнения: priority_que…   2.05.2008 23:08
first_day   Все получилось с multiset'ом Спасибо :) Вот чт…   2.05.2008 23:21
volvo   Смотри... В файле queue приоритетная очередь опред…   2.05.2008 23:38
first_day   Класс, и памяти в 3 раза меньше потратилось. :goo…   2.05.2008 23:39
first_day   Понятней стало, спасибо :)   3.05.2008 0:11


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 16:17
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name