На С++!! Блины
Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача.
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
Answers & Comments
Ответ:
#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;
}
Объяснение: