Алфавитный указатель

После теннисного турнира каждому игроку задавали вопрос, сколько матчей у него было. Спортсмен не может играть более одного матча с другим спортсменом. В качестве входных данных единственное, что у вас есть, это количество спортсменов и матчи каждого спортсмена. В качестве выхода у вас будет 1, если турнир можно будет сделать в соответствии с ответами спортсменов или 0, если нет. Например:

Input: 4 3 3 3 3      Output: 1  
Input: 6 2 4 5 5 2 1  Output: 0  
Input: 2 1 1          Output: 1  
Input: 1 0            Output: 0  
Input: 3 1 1 1        Output: 0  
Input: 3 2 2 0        Output: 0  
Input: 3 4 3 2        Output: 0

первый номер входа не входит в состав спортсменов, на него отвечает количество спортсменов, принимавших участие в турнире, например, в 6 2 4 5 5 2 1 у нас есть 6 спортсменов, которые принимали участие, и их ответы были 2 4 5 5 2 1.

Пока это то, что мы написали, но не получилось так хорошо:

import java.util.Scanner;
import java.util.Arrays;

public class Tennis {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        String N;
        int count;
        int sum = 0;
        int max;
        int activeAthletes;
        int flag;

        System.out.printf("Give: ");
        N = input.nextLine();

        String[] arr = N.split(" ");
        int[] array = new int[arr.length];

        for (count = 0; count < arr.length; count++) {
            array[count] = Integer.parseInt(arr[count]);
            //System.out.print(arr[count] + " ");
        }

        for (count = 1; count < arr.length; count++) {
            sum += array[count];
        }
        //System.out.println("\n" + sum);

        activeAthletes = array[0];

        for (count = 1; count < array.length; count++) {
            if (array[count] == 0) {
                activeAthletes--;
            }
        }

        max = array[1];
        for (count = 2; count < array.length; count++) {
            if (array[count] > max) {
                max = array[count];
            }
        }
       // System.out.println(max);

        if ((sum % 2 == 0) && (max < activeAthletes)) {            
            flag = 1;
        } else{
            flag = 0;
        }

        System.out.println(flag);
    }
}

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

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

Ответы

Ответ 1

Не уверен, что он работает на 100%, я бы хотел:

Сортировка ввода
для каждого элемента, идущего справа налево в массиве (от большего до меньшего)
- на основе значения n элемента в индексе я уменьшает n левых элементов на 1
- return fail, если вы не можете уменьшить, потому что вы достигли конца списка или значения 0
вернуть успех.

Эта логика (если она правильная) может привести к некоторым изменениям в решении O (N * log (N)), но в настоящее время я думаю, что это было бы слишком много для начинающего программиста.

EDIT:

Это не работает правильно на входе
2 2 1 1

Затем все шаги (без сортировки):

а любой элемент в списке L не 0:
- найти наибольший элемент N в списке L
- уменьшить N других значений в списке L на 1, если значение >= 1 (не уменьшать этот самый большой элемент)
  - return fail, если сбой на этом этапе
- установите этот элемент N на 0
return OK

Ответ 2

Вот подсказка. Ответьте на эти вопросы.

Учитывая N спортсменов, каково максимальное количество матчей?
Учитывая спортсмена X, каково максимальное количество матчей, которое он мог сделать?
Достаточно ли этого проверить? Если вы не уверены, попробуйте написать программу, чтобы создать все возможные соответствия игроков и проверить, удовлетворяет ли хотя бы один вход. Это будет работать только для небольших # ателетов, но это хорошее упражнение. Или просто сделайте это вручную.

Еще один способ задать этот вопрос, можно ли создать симметричную матрицу из 1s и 0s, строки которой равны значениям. Это будет таблица "кто играл кто". Подумайте об этом, как сетка N на N, где сетка [i] [j] = сетка [j] [i] (если вы играете с кем-то, кого вы играете) и сеткой [i] [i] = 0 (никто не играет сам)

Например

Input: 4 3 3 3 3 Output: 1

Похож на

Мы не можем сделать это с этим, хотя: Вход: 3 2 2 0 Выход: 0

ИЗМЕНИТЬ

Это эквивалентно этому (из Степень (теория графов))

Гамими (1962) доказал, что (d1, d2,..., dn) является степенной последовательностью a простой граф тогда и только тогда, когда (d2 - 1, d3 - 1,..., dd1 + 1 - 1, dd1 + 2, dd1 + 3,..., dn). Этот факт приводит к простому алгоритму поиска простой граф, который имеет заданную реализуемую последовательность степеней:
Начните с графа без краев.

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

Подключите первую вершину к следующим вершинам d1 в этом списке, а затем удалите ее из списка. Повторно сортировать список и повторять до тех пор, пока все Требования к степени удовлетворены.
Задача нахождения или оценки числа графов с заданным Последовательность степеней является проблемой из поля перечисление графа.

Ответ 3

Возможно, вы можете взять массив совпадений матчей спортсменов и определить наибольшее количество там.

Затем посмотрите, можете ли вы разбить это число на 1 и вычесть их из нескольких других элементов массива.

Извлеките этот массив с наибольшим числом и удалите его из массива и обновите остальные члены с уменьшенными значениями.

Теперь повторите процесс - определите новое наибольшее число и вычтите его из других членов массива.

Если в какой-либо точке не хватает элементов массива для вычитания 1 из, то возвращайте приложение 0. В противном случае продолжайте делать это, пока в массиве не будет больше членов, после чего вы сможете вернуть приложение 1.

Кроме того, не забудьте удалить элементы массива, которые были уменьшены до нуля.

Ответ 4

Изменить: ниже решение передает некоторые недопустимые входы как действительные. Это быстрый способ проверить определенные негативы, но он допускает ложные срабатывания.

Вот что предложил бы математик:

Сумма совпадений должна быть четной. 3 3 4 2 1 суммируется до 13, что подразумевает, что кто-то сыграл матч против себя.
Для игроков n, если в каждом матче исключается один игрок не менее n-1, должны быть сыграны различные совпадения. (Турнир с нокаутом.) Чтобы увидеть это, нарисуйте дерево матчей для игроков 2, 4, 8, 16, 32..., требующих 1, 3, 7, 31... совпадений, чтобы решить победителя.
Для игроков n максимальное количество совпадений, если каждый играет каждый раз, не принимая повторных совпадений, составляет n choose 2 или (n!)/(2!)(n-2)! (турнир Round Robin). n! - факториальная функция, n! = n * n-1 * n-2 * ... * 3 * 2 * 1..

Итак, критерии:

Сумма количества совпадений должна быть четной.
Сумма количества совпадений должна быть не менее 2n-2. (Обратите внимание на умножение на 2 - каждое совпадение приводит к тому, что оба игрока увеличивают свой счет на единицу.)
Сумма количества совпадений должна быть не более 2 * n choose 2.
[Изменить] Каждый игрок должен участвовать хотя бы в одном матче.

Если ваш турнир является перекрестком между турниром нокаутом и турниром с круговым движением, вы можете найти где-то между n-1 и n choose 2.

Edit:

Если какой-либо игрок играет больше, чем n-1, он играл не менее двух раз.

Если ваш турнир является турниром с нокаутом, заказанным так, чтобы каждый игрок участвовал в как можно меньшем количестве матчей, то каждый игрок может участвовать не более чем в log_2(n) матчах или так (возьмите log base 2 и округлите вверх.) В турнир с 16 игроками, максимум 4 матча. В турнире из 1024 игроков, максимум 10 матчей.

Ответ 5

Ваши примеры можно тривиально решить, посчитав совпадения и посмотрев, делятся ли они на 2.

Проблема, не охваченная вашими примерами, будет игроком, у которого больше игр, чем сумма других игроков:

Вход: 4 5 1 1 1 Выход: 0

Это может быть сложно, если добавить еще игроков:

Вход: 6 5 5 5 1 1 1 Выход: 0

Как решить этот вопрос? Ну, удалите одну игру попарно из максимального и минимального игрока и посмотрите, что произойдет:

Вход: 6 5 5 5 1 1 1
Вход: 5 5 5 4 1 1 -
Вход: 4 5 4 4 1 - -
Вход: 3 4 4 4 - - -

Он нарушает правило:

Спортсмен не может играть более одного матча с другим спортсменом.

Если осталось 3 игрока, у них не может быть более двух игр.