Пусть турнир назначен на этаже X.
На этажах 1…X живут L’ людей, на этажах X+1…N — H′ людей.
Вопрос 1. Стоит ли переносить турнир на этаж X+1?
Тогда для L′ людей добавляется лишний этаж, для H′ — исчезает лишний этаж, и выигрыш будет H′−L′.
Стоит, если H′ > L′. Не стоит, если H′ < L′. Безразлично, если H′ = L′.
Вопрос 2. Возможно ли такое: вверх на 1 перенести не удаётся (будет хуже или безразлично), но этаж Y > X оптимальнее (строго)?
Раз вверх на 1 перенести нельзя, то H’ <= L’.
Если этаж Y − 1 безразличен с Y, перенесём турнир туда. Если Y − 2 тже безразличен, то туда, и т.д. Остановимся на этаже Z. Видно, что Z > X + 1: если мы в результате этих движений добрались до X+1, то он лучше X, противоречие.
Раз Z — оптимальный этаж, то у этажа Z−1 > X есть свои L″ и H″, и поскольку с Z−1 на этаж вверх перенести всё же можно, то H″ > L″.
С другой стороны, при повышении этажа увеличивается L и уменьшается H, и L″ >= L′ >= H‘ >= H″, то есть H″ <= L″. Противоречие.
Следствие 3. Если турнир выгодно перенести на несколько этажей выше/ниже, то его выгодно перенести и на этаж выше/ниже.
Задача 4. Пусть на этажах 1…X−1 живут L людей, на этаже X — M людей, на этажах X+1…N — H людей.
Для простоты считаем, что сверху и снизу есть по фиктивному пустому этажу — то есть теоретически можно (на практически неоптимально) проводить турнир в подвале и на чердаке.
Задачу с переносом турнира вверх мы уже решали, и условие того, что турнир нельзя (или безразлично) перенести на этаж вверх: H <= L + M.
Условие того, что турнир можно (или безразлично) перенести с этажа X−1: H + M >= L.
Поскольку H + M + L = N (кол-во людей), то эти условия можно записать в виде: L + M >= N/2, L <= N/2
(всё, получили чеканное условие, и ключи от чердака и подвала можно отдать техслужбам гостиницы.)
Решение: Идём по этажам, считаем людей. Где накопится N/2, там проводим турнир.
// считаем полное кол-во
N = 0
для i = [0..nFloors)
N += a[i]
// ищем, где половинка N
sum = 0;
для i = [0..nFloors)
sum += a[i]
если sum * 2 >= N
вывести: i
СТОП
Расширенное решение: Если накопилось
ровно N/2, безразличны данный этаж, все нулевые над ним, и ещё один ненулевой. (Можно без кода?)
