Структуры, heap, C++ Опции

[first_day]

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

Есть (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

[volvo]

Быстрее не быстрее, но 10-кратное ускорение на твоем же векторе можно получить не напрягаясь:

#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);

	int n, j;
	vector<double> v;
	in >> n;

	for(int i = 0; i < n; i++) {
	    in >> j;
		v.push_back((double)j);
	}

	double s = 0.0;
	while (n > 1)
	{
		vector<double>::iterator i_min, i_max;
		double mini_1 = *(i_min = min_element(v.begin(), v.end()));
		v.erase(i_min);
		double mini_2 = *(i_max = min_element(v.begin(), v.end()));
		v.erase(i_max);

		double sum_two = (mini_1 + mini_2);
		s += sum_two / (double)100 * 5;
		v.push_back(sum_two);
		n -= 1;
	}
	out << s;
	out.close();
	return 0;
}

Откуда берется ускорение понимаешь?