7537. Популярный голос

При проведении выборов с более чем двумя кандидатами часто бывает, что победитель (кандидат, набравший наибольшее количество голосов) получает меньше, чем большинство голосов. По заданным результатам выборов Вам необходимо определить победителя, а также определить, получил ли победитель более половины голосов?

Вход. Первая строка содержит количество тестов t (t ≤ 500). Первая строка каждого теста содержит натуральное число – количество кандидатов n на выборах. Далее следуют n строк, i-ая из которых содержит количество голосов, отданных за i-го кандидата.

В каждом тесте имеется как минимум 2 и не более 10 кандидатов, каждый кандидат может получить не более 50 000 голосов.

Выход. Результат каждого теста вывести в отдельной строке. Если победитель получил более половины голосов, вывести фразу "majority winner" и номер кандидата - победителя. Если победитель не получил более половины голосов, вывести фразу "minority winner" и номер кандидата - победителя. Если победителя определить невозможно из-за того что ни один из кандидатов не получил больше голосов чем другие, вывести фразу "no winner". Кандидаты нумеруются числами 1, 2, ..., n.

Пример входа	Пример выхода
4 3 10 21 10 3 20 10 10 3 10 10 10 4 15 15 15 45	majority winner 2 minority winner 1 no winner minority winner 4

РЕШЕНИЕ

линейный массив

Анализ алгоритма

Вычислим общее количество голосов s отданных за кандидатов. Найдем кандидата id, получившего наибольшее количество голосов max. Если max голосов получило более одного кандидата, то победителя нет. Если 2 * max > s, то победитель id получил более половины голосов и является "majority winner". Иначе кандидат id является "minority winner".

Реализация алгоритма

Количество голосов за кандидатов храним в массиве mas.

int mas[11];

Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

memset(mas,0,sizeof(mas));

Общее количество отданных голосов подсчитываем в переменной s. Ищем номер кандидата id, за которого отдано наибольшее количество голосов max.

for(s = max = 0, i = 1; i <= n; i++)

{

scanf("%d",&mas[i]);

s += mas[i];

if (mas[i] > max)

{

max = mas[i];

id = i;

}

}

В переменной cnt подсчитаем, сколько кандидатов получило наибольшее число голосов max.

for(cnt = 0, i = 1; i <= n; i++)

if (mas[i] == max) cnt++;

Если ни один из кандидатов не набрал голосов больше чем другие (cnt больше 1), то победителя нет.

if (cnt > 1)

printf("no winner\n");

Если 2 * max > s, то победитель id получил более половины голосов.

else if (2 * max > s)

printf("majority winner %d\n",id);

else

printf("minority winner %d\n",id);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String []args)

{

int mas[] = new int[11];

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int cnt, i, s, max, id = 0, n = con.nextInt();

Arrays.fill(mas,0);

for(s = max = 0, i = 1; i <= n; i++)

{

mas[i] = con.nextInt();

s += mas[i];

if (mas[i] > max)

{

max = mas[i];

id = i;

}

}

for(cnt = 0, i = 1; i <= n; i++)

if (mas[i] == max) cnt++;

if (cnt > 1)

System.out.println("no winner");

else if (2 * max > s)

System.out.println("majority winner " + id);

else

System.out.println("minority winner " + id);

}

}

}