Задача 574А

Лимак — это мишка гризли, жаждущий власти и признания. Он хочет победить в предстоящих выборах и править всей Берляндией.

Дано n кандидатов, включая Лимака. Мы знаем, сколько граждан собираются проголосовать за каждого кандидата, за i-го кандидата будет отдано ai голосов. Лимак — кандидат номер 1. Чтобы победить на выборах, он должен набрать строго больше голосов, чем любой другой кандидат.

Победа важнее всего, так что Лимак решил сжульничать. Он подкупит некоторых граждан и украдет голоса у своих оппонентов. Чтобы подкупить гражданина, Лимак должен дать ему одну конфетку: граждане — мишки, а мишкам нравятся конфетки. У Лимака немного конфеток и ему интересно, сколько граждан ему надо подкупить?

Входные данные

В первой строке записано единственное целое число n (2 ≤ n ≤ 100) — количество кандидатов.

Во второй строке записано n целых чисел через пробел, a1, a2, …, an (1 ≤ ai ≤ 1000) — количество голосов за каждого кандидата. Лимак — кандидат номер 1.

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

Выходные данные

Выведите минимальное количество граждан, которых Лимак должен подкупить, чтобы набрать строго больше голосов, чем любой другой кандидат.

Примеры тестов
входные данные

выходные данные

входные данные

выходные данные

входные данные

выходные данные

Примечание

В первом тесте у Лимака 5 голосов. Один из способов достичь победы — подкупить 4 граждан, желающих проголосовать за третьего кандидата. Количество голосов будет 9, 1, 7, 2, 8 (У Лимака будет 9 голосов). Другой способ — отнять 3 голоса у третьего кандидата и 1 голос у второго кандидата, чтобы получилась следующая ситуация: 9, 0, 8, 2, 8.

Во втором примере Лимак украдет 2 голоса у каждого кандидата. Получится: 7, 6, 6, 6.

В третьем примере Лимак одержит победу, не подкупив ни одного гражданина.

Моё решение:

Решение заключается в том, что мы в первом цикле блока while сперва находим за кого больше всего проголосовали, тут же проверяем есть ли кто-то, кто набрал больше голосов, если да то уменьшаем переменную isResult.

Затем если есть тот кандидат, кто набрал больше всех, с него убираем один голос в пользу нашего кандидата и возвращаемся в начало цикла while.

Из цикла while не выйдем, пока есть хоть кто-то, кто набрал больше первого кандидата.

 

(Просмотров всего: 175, просмотров сегодня: 1)

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *