0

Всем добрый день! Есть задача: Роман состоит из C глав. Нужно, не переставляя главы, разбить его на B (В<С) томов так, чтобы максимальная толщина тома (сумма количеств страниц вошедших в него глав) была как можно меньше. Каждую главу начинают с новой страницы, поэтому толщина тома есть сумма длин глав, входящих в него. Разрывать главы нельзя. Если есть несколько равноценных оптимальных решений, вывести любое из них. 10 Вход. В первой строке текста - количества С и В, в следующих С строках - длины глав. 3≤В≤40, В≤С≤250, суммарное число страниц не больше 3x104. Выход. В первой строке - максимальная толщина тома, в следующих В строках - номера первой и последней глав каждого тома. Например, если пять глав имеют длины 300, 300, 500, 300, 300 и распределяются по трем томам, то максимальная толщина тома - 600, первый том начинается главой 1 и заканчивается 2, второй включает только главу 3, третий - главы 4 и 5.

Сама функция есть и она работает, только я никак не могу додуматься, как сделать деление на главы? Код прикладываю ниже:

#include <iostream>
#include <vector>

using namespace std;

int c, b;
vector<int>a, pref;

int Summ(int Start, int Finish)
{
    return pref[Finish + 1] - pref[Start];
}

int Razbienie(int begin, int end)
{
    if (end == 0)
    {
        return Summ(begin, c - 1);
    }
    else
    {
        int m = 3e4;
        for (int i = begin + 1; i <= c - end; i++)
        {
            m = min(m, max(Razbienie(i, end - 1), Summ(begin, i - 1)));
        }
        return m;
    }
}

int main()
{
    setlocale(0, "");
    cout << "Введите количество глав и томов:"<<endl;
    cin >> c >> b;
    a.resize(c);
    pref.resize(c + 1);
    cout<< "Введите длину каждой главы:"<<endl;
    for (int i = 0; i < c; i++)
    {
        cin >> a[i];
        pref[i + 1] = pref[i] + a[i];
    }
    cout << "Максимальный размер тома - "<< Razbienie(0, b - 1)<<endl;
    return 0;
}
4
  • Я бы не советовал основываться на таком коде. Во вторых не ясно, что такое длина главы, непонятно что значит " границы томов, которые входят в каждый из томов" 30 июн 2019 в 10:25
  • Извините за ошибки. Другого кода к сожалению нет, поджимают сроки( У нас есть допустим 10 глав одной истории (в них сколько то слов), их нужно разделить на 4 тома. Нужно с помощью рекурсии сначала найти максимальное количество слов в одном томе (главное - нельзя делить главы), а затем распределить главы на каждый том по порядку. Как я указал в примере. 30 июн 2019 в 10:31
  • а почему пераый том не может содержать больше одной главы? И вопрос не только в этом. Но в общем вам наверное нужно где то хранить длины каждой главы и начинать разбирать все возможные варианты. 30 июн 2019 в 11:10
  • @ARHovsepyan необходимо сделать размер тома минимальным, но так, чтобы все тома были одинакового размера и все главы были распределены по томам. Ещё раз исправил описание, полностью скопировав задачу. 30 июн 2019 в 11:17

1 ответ 1

0

Функция Razbienie у Вас фактически заполняет двумерную таблицу размером BxC (в явном виде она не хранится, только как локальные переменные рекурсивной функции).

Чтобы вернуть само разбиение, нужно завести таблицу переходов, использовать свои условия вместо библиотечных min/max функций, и в зависимости от выполняемой ветви if-оператора запоминать в каждой ячейке таблицы, откуда в неё пришли.

После нахождения лучшего разбиения пройти из конечной ячейки по запомненным переходам.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.