![]() |
1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!
![]() |
first_day |
![]() ![]()
Сообщение
#1
|
![]() Пионер ![]() ![]() Группа: Пользователи Сообщений: 86 Пол: Мужской Реальное имя: Илья Репутация: ![]() ![]() ![]() |
Передо мной стоит следующая задача:
Есть (N<10^5) чисел, на каждом шаге алгоритма нужно находить 2 минимальных числа и заменять их на их сумму. Так делается до тех пор, пока не останется одно число. Сделать то я сделал, вот только работает это долго. Знаю, что есть такая структура данных как куча, которая выдает минимальный элемент за O(1) и добавляет за O(log N). Но как это реализовывать не знаю, не нашел. А то, что находил, было совсем не понятно... возможно потому, что никогда не работал со структурами. Может это можно реализовать на простом массиве? Помогите, кто может. ![]() 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 - 2.05.2008 16:54 -------------------- Я бы изменил мир, да Бог не дает исходников.
|
![]() ![]() |
![]() |
Текстовая версия | 19.07.2025 3:11 |