Question

На С++!! Блины Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача. N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai. Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально. Гости хотят переложить блины таким образом, чтобы после перекладывания они съели все блины за минимальное время (которое равно наибольшему числу блинов на тарелках у гостей, включая нового гостя). Определите, за какое наименьшее время гости смогут съесть свои блины после перекладывания. Входные данные Программа получает на вход натуральное число N, не превосходящее 100000 – первоначальное количество гостей. Следующие N строк содержат натуральные числа ai – количество блинов на тарелке i-го человека. Значения ai даны в порядке неубывания, то есть ai≤ai+1 . Сумма значений всех ai не превосходит 2⋅109. Выходные данные Программа должна вывести одно целое число — минимальное время, за которое все гости закончат есть свои блины после перекладывания части блинов на тарелку нового гостя. Пояснение к примеру За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний — 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов. Примеры Ввод Вывод 4 1 3 5 6 4

Answer 1

Ответ:

#include <iostream>

using namespace std;

int main()

{

   int N;

   cin >> N;

   int* arr = new int[N];

   for (int i(0); i < N; ++i) cin >> arr[i];

   int count(N - 1);

   int result = 0;

   for (; count >= 0 && result < arr[count]; --count) {

       if (count > 0) result += arr[count] - arr[count - 1];

   }

   int sum = 0;

   for (int i(count + 1); i < N; ++i) sum += arr[i];

   result = sum / (N - count);

   if (sum > result*(N - count)) ++result;

   cout << result;

}

Объяснение:

Answer 2

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

Вашей целью является минимизация этого максимального количества блинов на тарелке после перекладывания. Для этого вы можете использовать бинарный поиск, чтобы найти минимальное возможное значение этого максимального количества блинов.

Вот пример кода на C++, который решает эту задачу:

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

// Функция для проверки, можно ли закончить есть блины в заданное время
bool canFinishEating(vector<int>& plates, int time, int newGuestBlinCount) {
    int n = plates.size();
    int remainingTime = time;

    for (int i = n - 1; i >= 0; i--) {
        int blinCount = plates[i];
        if (blinCount > time) {
            // Новый гость не может съесть так много блинов
            int diff = blinCount - time;
            if (i == n - 1) {
                // Если это последний гость, он перекладывает блины новому гостю
                newGuestBlinCount += diff;
            } else {
                // Иначе перекладываем блины себе и новому гостю
                int transfer = min(remainingTime, diff);
                newGuestBlinCount += transfer;
                remainingTime -= transfer;
            }
        } else {
            // Гость съел все блины за время time
            remainingTime -= time - blinCount;
        }

        if (remainingTime < 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> plates(n);

    for (int i = 0; i < n; i++) {
        cin >> plates[i];
    }

    int left = 0, right = plates[n - 1], result = right;

    // Используем бинарный поиск для нахождения минимального времени
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (canFinishEating(plates, mid, 0)) {
            // Если можно закончить есть блины за время mid, уменьшаем время
            result = mid;
            right = mid - 1;
        } else {
            // Иначе увеличиваем время
            left = mid + 1;
        }
    }

    cout << result << endl;

    return 0;
}

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