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

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

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

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

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#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 минуты
Вообще я ещё вчера всё-таки смог сдать с прохождением всех тестов

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

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .