Передо мной стоит следующая задача:
Есть (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;
}
немного не то написал, через час покажу на примере.
в общем мой пример уже смысла не имеет
Быстрее не быстрее, но 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;
}
Ну общий принцип вроде как да... Т.е. находим 2 минимальных элемента, а не соритруем, так?
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);
Знать бы что такое multiset...
интересное дело Вот смотри: http://www.cplusplus.com/reference/stl/multiset/
надо попробовать, может будет быстрее.
По-моему я уже давал тебе ссылку на этот сайт: http://www.cplusplus.com/reference/stl/multiset/
priority_queue< double, vector<double>, greater<double> > q;
#include <fstream>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
ifstream in("input6.txt");
ofstream out("output6.txt");
out.setf(ios::fixed);
out.precision(2);
int n, j;
in >> n;
priority_queue< double, vector<double>, greater<double> > q;
for(int i = 0; i < n; i++) {
in >> j;
q.push((double)j);
}
double s = 0.0;
while (n > 1)
{
double min_1 = q.top(); q.pop();
double min_2 = q.top(); q.pop();
double sum_two = (min_1 + min_2);
s += sum_two / (double)100 * 5;
q.push(sum_two);
n -= 1;
}
out << s;
out.close();
return 0;
}
Все получилось с multiset'ом Спасибо
Вот что я написал: (за 0.5 секунды прошло)
#include <fstream>
#include <set>
#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;
multiset<double> m;
in >> n;
for(int i = 0; i < n; i++)
{
in >> j;
m.insert((double)j);
}
double s = 0.0;
while (n > 1)
{
multiset<double>::iterator i_min, i_max;
double mini_1 = *(i_min = m.begin());
m.erase(i_min);
double mini_2 = *(i_max = m.begin());
m.erase(i_max);
double sum_two = (mini_1 + mini_2);
s += sum_two / (double)100 * 5;
m.insert(sum_two);
n -= 1;
}
out << s;
out.close();
return 0;
}
namespace std {, то есть, первый параметр - это тип элементов, с которым будет работать priority_queue, второй - тип контейнера, в котором все данные будут храниться внутри priority_queue (по умолчанию - vector<того_же_типа>), а третий - критерий сортировки. По умолчанию используется less<тип_элемента_контейнера>, тебе понадобилось "обратное" поведение, значит, меняем на greater<double>.
template <class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type> >
class priority_queue;
}
Класс, и памяти в 3 раза меньше потратилось.
Понятней стало, спасибо