Лимак — это мишка гризли, жаждущий власти и признания. Он хочет победить в предстоящих выборах и править всей Берляндией.
Дано n кандидатов, включая Лимака. Мы знаем, сколько граждан собираются проголосовать за каждого кандидата, за i-го кандидата будет отдано ai голосов. Лимак — кандидат номер 1. Чтобы победить на выборах, он должен набрать строго больше голосов, чем любой другой кандидат.
Победа важнее всего, так что Лимак решил сжульничать. Он подкупит некоторых граждан и украдет голоса у своих оппонентов. Чтобы подкупить гражданина, Лимак должен дать ему одну конфетку: граждане — мишки, а мишкам нравятся конфетки. У Лимака немного конфеток и ему интересно, сколько граждан ему надо подкупить?
В первой строке записано единственное целое число n (2 ≤ n ≤ 100) — количество кандидатов.
Во второй строке записано n целых чисел через пробел, a1, a2, …, an (1 ≤ ai ≤ 1000) — количество голосов за каждого кандидата. Лимак — кандидат номер 1.
Обратите внимание, что после подкупа количество голосов за некоторого кандидата может равняться нулю или может превышать1000.
Выведите минимальное количество граждан, которых Лимак должен подкупить, чтобы набрать строго больше голосов, чем любой другой кандидат.
|
1 2 |
5 5 1 11 2 8 |
|
1 |
4 |
|
1 2 |
4 1 8 8 8 |
|
1 |
6 |
|
1 2 |
2 7 6 |
|
1 |
В первом тесте у Лимака 5 голосов. Один из способов достичь победы — подкупить 4 граждан, желающих проголосовать за третьего кандидата. Количество голосов будет 9, 1, 7, 2, 8 (У Лимака будет 9 голосов). Другой способ — отнять 3 голоса у третьего кандидата и 1 голос у второго кандидата, чтобы получилась следующая ситуация: 9, 0, 8, 2, 8.
Во втором примере Лимак украдет 2 голоса у каждого кандидата. Получится: 7, 6, 6, 6.
В третьем примере Лимак одержит победу, не подкупив ни одного гражданина.
Моё решение:
Решение заключается в том, что мы в первом цикле блока while сперва находим за кого больше всего проголосовали, тут же проверяем есть ли кто-то, кто набрал больше голосов, если да то уменьшаем переменную isResult.
Затем если есть тот кандидат, кто набрал больше всех, с него убираем один голос в пользу нашего кандидата и возвращаемся в начало цикла while.
Из цикла while не выйдем, пока есть хоть кто-то, кто набрал больше первого кандидата.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
var N = readline(); var data = readline().split(' '); var kondidate = new Array(); var bribed=0; var isResult=0; for (i=0;i<N;i++){ kondidate[i] = parseInt(data[i]); } //пока есть ктото, кто набрал больше while (isResult<N-1){ isResult=N-1; var maxNumber = 0; var maxValue = kondidate[0] ; //находим за кого больше всего проголосовало for (i=1;i<N;i++){ if (maxValue<=kondidate[i]){ maxNumber=i; maxValue=kondidate[i]; isResult--; } } //снимаем один голос с оппонента, набравшего максимум голосов if (maxNumber!=0){ kondidate[0]++; bribed++; kondidate[maxNumber]--; } } write(bribed); |