Жадная последовательность

@Hirurg2605 · Регистрация: 29.08.2012

Author24 — интернет-сервис помощи студентам

Здравствуйте! Есть задача, над решением которой бьюсь несколько дней, но никак не могу дойти до правильного решения. Полный текст задания можно посмотреть на сайте, если вкратце, то смысл такой:

Дана последовательность из N целых чисел a_i. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.
Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.

Программа тестируется на сайте, вот самый успешный на данный момент вариант кода:

C++

#include <iostream>
#include <fstream>
 
using namespace std;
 
int main()
{
    ifstream fin("input.txt");
    if (!fin.is_open())
    {
        cout << "open file error" << endl;
        return -1;
    }
 
    int n, m;
    fin >> n;
    fin >> m;
 
    int *a = new int [n];
    for (int i = 0; i < n; ++i) {
        fin >> a[i];
    }
    fin.close();
 
    // часть для тестирования
    //delete[] a;
    //n = m = 100000;
    //a = new int [n];
    //for (int i = 0; i < n; ++i)
    //  a[i] = rand() % 20001 - 10000;
 
    int mi = 0;
    int j1, j2, a1, a2, a3;
 
    while (n > 1 && mi < m) 
    {
        if (a[0] < a[1])
        {
            j1 = 0; a1 = a[j1];
            j2 = 1; a2 = a[j2];
        }
        else
        {
            j1 = 1; a1 = a[j1];
            j2 = 0; a2 = a[j2];
        }
 
        for (int j = 2, *aj = &a[2]; j < n; j ++, aj ++) 
        {
            if (*aj < a2)
            {
                if (*aj < a1)
                {
                    a2 =  a1; j2 = j1;
                    a1 = *aj; j1 = j;
                }
                else
                {
                    a2 = *aj; j2 = j;
                }
            }
        }
 
        if (j1 > j2) {
            a3 = j1;
            j1 = j2;
            j2 = a3;
        }
 
        if (j1 < j2 - 1)
            memmove(&a[j1], &a[j1 + 1], (j2 - j1 - 1) * sizeof(int));
        
        if (j2 < n - 1)
            memmove(&a[j2 - 1], &a[j2 + 1], (n - j2 - 1) * sizeof(int));
 
        //for (int j = j1; j < j2 - 1; j ++)
        //  a[j] = a[j + 1];
 
        //for (int j = j2 - 1; j < n - 2; j ++)
        //  a[j] = a[j + 2];
 
        a[n - 2] = a1 + a2;
        n --;
        mi ++;
    }
 
    ofstream fout("output.txt");
    if (!fout.is_open())
    {
        cout << "open file error" << endl;
        return -2;
    }
 
    for (int i = 0; i < n; ++i) {
        fout << a[i] << " ";
    }
    fout.flush();
    fout.close();
 
    delete[] a;
    return 0;
}

но проблема в том, что этот код не проходит тесты по времени, а ограничения по переменным достаточно большие:
1 ≤ M < N ≤ 10⁵, −10⁴ ≤ a_i ≤ 10⁴.
Преподаватель говорит, что нужно использовать структуру "куча". Я попытался написать ещё одну версию, но она работает ещё медленнее:

C++

#include <iostream>
#include <fstream>
 
#include <functional>
#include <queue>
#include <cstdint>
 
using namespace std;
 
struct Elem
{
    int64_t value;
    int index;
 
    Elem (int64_t v, int i)
    {
        value = v;
        index = i;
    }
};
 
struct comp_val
{
    bool operator()(const Elem& a, const Elem& b)
    {
        if (a.value == b.value)
            return (a.index > b.index);
        else
            return (a.value > b.value);
    }
};
 
struct comp_index
{
    bool operator()(const Elem& a, const Elem& b)
    {
        return (a.index > b.index);
    }
};
 
int main()
{
    priority_queue<Elem, vector<Elem>, comp_val> q;
 
    ifstream fin("input.txt");
    if (!fin.is_open())
    {
        cout << "open file error" << endl;
        return -1;
    }
 
    int n, m, val;
    fin >> n;
    fin >> m;
 
    for (int i = 0; i < n; ++i) {
        fin >> val;
        q.push(Elem(val, i));
    }
    fin.close();
 
    // n = m = 100000;//00;
    // for (int i = 0; i < n; ++i)
    // {
        // val = rand() % 20001 - 10000;
        // q.push(Elem(val, i));
    // }
 
    int sum;
    for (int mi = 0; mi < m && q.size() > 2; mi ++)
    {
        //cout << "Step " << mi + 1 << endl;
        //cout << "removed a[" << q.top().index << "] = " << q.top().value << endl;
        sum = q.top().value;
        q.pop();
 
        //cout << "removed a[" << q.top().index << "] = " << q.top().value << endl;
        sum += q.top().value;
        q.pop();
        
        //cout << "appended a[" << n << "] = " << sum << endl;
        q.push(Elem(sum, n ++));
    }
    
    priority_queue<Elem, vector<Elem>, comp_index> q_out;
 
    // сортировка по индексу
    while (!q.empty()) {
        q_out.push(q.top());
        q.pop();
    }
 
    ofstream fout("output.txt");
    if (!fout.is_open())
    {
        cout << "open file error" << endl;
        return -2;
    }
 
    while (!q_out.empty()) {
        fout << q_out.top().value << " ";
        //fout << a[i] << " ";
        q_out.pop();
    }
    fout.flush();
    fout.close();
 
    return 0;
}

Подскажите, что я делаю не так, может быть нужно писать свою реализацию кучи или что-то ещё, я в отчаянии

@oleg-m1973 · 08.06.2019, 14:18

Сообщение от Hirurg2605

я замеряю только для относительного сравнения разных версий, замерять максимальную скорость в абсолютно точных значениях не вижу смысла, т.к. время на сервере всё равно будет отличаться

Так и замеряй в релизной, относительную. В дебажной - даже относительная будет кривой

Добавлено через 1 минуту

Сообщение от Hirurg2605

это как раз создание нового элемента с индексом "правее" всех остальных и значением равным сумме удалённых

А там разве не надо удалять одинаковые минимальные?

@Hirurg2605 · 08.06.2019, 14:20 **[ТС]**

Сообщение от oleg-m1973

А там разве не надо удалять одинаковые минимальные?

надо, но чтобы не пересчитывать индексы всех существующих элементов после удаления минимальных (а они могут быть в середине и где угодно) я добавляю новый элемент с заведомо максимальным индексом и он оказывается как бы правее всех остальных

@oleg-m1973 · 08.06.2019, 21:58

Сообщение от Hirurg2605

надо, но чтобы не пересчитывать индексы всех существующих элементов после удаления минимальных (а они могут быть в середине и где угодно) я добавляю новый элемент с заведомо максимальным индексом и он оказывается как бы правее всех остальных

Там вроде сортированный массив, они не могут быть в середине.
И что значит "пересчитывать индексы", зачем их пересчитывать?

@Hirurg2605 · 09.06.2019, 10:43 **[ТС]**

Сообщение от oleg-m1973

зачем их пересчитывать?

вот как влияет порядок элементов на результат:
0) 1 1 2 3 4
1) 2 3 4 2
2) 3 4 4
3) 4 7
4) 11
второй вариант
0) 1 4 2 1 3
1) 4 2 3 2
2) 4 3 4
3) 4 7
4) 11
Так вот, числа изначально те же, но порядок разный. И последовательности вплоть до последнего шага отличаются, а наш алгоритм выполняется M < N шагов, т.е. если не хранить порядок элементов, то мы получим некорректный результат.

Добавлено через 2 минуты
Вообще я ещё вчера всё-таки смог сдать с прохождением всех тестов

Так что большое спасибо за подсказки, возможно мы не везде правильно друг друга поняли, но вы задали мне нужное направление

@Hirurg2605 0 / 0 / 0 Регистрация: 29.08.2012 Сообщений: 59
	08.06.2019, 14:20 [ТС]	22
	Сообщение от oleg-m1973 А там разве не надо удалять одинаковые минимальные? надо, но чтобы не пересчитывать индексы всех существующих элементов после удаления минимальных (а они могут быть в середине и где угодно) я добавляю новый элемент с заведомо максимальным индексом и он оказывается как бы правее всех остальных 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	08.06.2019, 21:58	23
	Сообщение от Hirurg2605 надо, но чтобы не пересчитывать индексы всех существующих элементов после удаления минимальных (а они могут быть в середине и где угодно) я добавляю новый элемент с заведомо максимальным индексом и он оказывается как бы правее всех остальных Там вроде сортированный массив, они не могут быть в середине. И что значит "пересчитывать индексы", зачем их пересчитывать? 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	08.06.2019, 14:18	21
	Сообщение от Hirurg2605 я замеряю только для относительного сравнения разных версий, замерять максимальную скорость в абсолютно точных значениях не вижу смысла, т.к. время на сервере всё равно будет отличаться Так и замеряй в релизной, относительную. В дебажной - даже относительная будет кривой Добавлено через 1 минуту Сообщение от Hirurg2605 это как раз создание нового элемента с индексом "правее" всех остальных и значением равным сумме удалённых А там разве не надо удалять одинаковые минимальные? 0

@Hirurg2605 0 / 0 / 0 Регистрация: 29.08.2012 Сообщений: 59
	09.06.2019, 10:43 [ТС]	24
	Сообщение от oleg-m1973 зачем их пересчитывать? вот как влияет порядок элементов на результат: 0) 1 1 2 3 4 1) 2 3 4 2 2) 3 4 4 3) 4 7 4) 11 второй вариант 0) 1 4 2 1 3 1) 4 2 3 2 2) 4 3 4 3) 4 7 4) 11 Так вот, числа изначально те же, но порядок разный. И последовательности вплоть до последнего шага отличаются, а наш алгоритм выполняется M < N шагов, т.е. если не хранить порядок элементов, то мы получим некорректный результат. Добавлено через 2 минуты Вообще я ещё вчера всё-таки смог сдать с прохождением всех тестов Так что большое спасибо за подсказки, возможно мы не везде правильно друг друга поняли, но вы задали мне нужное направление 0