15

网球比赛结束后,每个球员都被问到他有多少场比赛。一名运动员不能与另一名运动员进行多于一场比赛。作为输入,您唯一拥有的是运动员人数和每位运动员参加的比赛。作为输出,如果可以根据运动员的回答完成比赛,则为 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);
    }
}

我不想要一个直接的解决方案,也许只是一些提示和提示,因为我们真的不知道还能做什么,我重复一遍,即使我会把它标记为家庭作业(因为我觉得版主会再次关闭它)它不是,这只是我兄弟发现的问题,我们正在努力解决。

好吧,你们中的许多人已经回答了,我真的很感激,但是因为我明天有工作,所以我需要睡觉,所以我明天可能会阅读其余的答案,看看有什么用

4

5 回答 5

7

不确定它是否100%有效,我会喜欢:

  1. 排序输入
  2. 对于数组中从右到左的每个元素(从大到小)

    • 基于索引 i 处元素的值 n 将 n 左元素减 1
    • 如果由于到达列表末尾或值 0 而不能减少,则返回失败
  3. 返回成功。

这种逻辑(如果正确)可以导致对 O(N*log(N)) 解决方案进行一些修改,但我目前认为这对于新手程序员来说太过分了。

编辑:


这在输入2 2 1 1上不起作用

然后所有步骤(没有排序):

  1. 而列表 L 中的任何元素都不为 0:

    • 在列表 L 中找到最大元素 N
    • 如果值 >= 1,则将列表 L 中的 N 个其他值减少 1(不减少此最大元素)
      • 如果在这一步失败,则返回失败
    • 将此元素 N 设置为 0
  2. 返回确定

于 2012-04-25T21:40:48.320 回答
5

这里有一个提示。回答这些问题

  1. 给定 N 名运动员,最多可以参加多少场比赛?
  2. 给定运动员 X,他最多可以做多少场比赛?
  3. 这足以检查这些吗?如果您不确定,请尝试编写一个程序来生成所有可能的玩家匹配,并检查是否至少有一个满足输入。这仅适用于少数运动员,但这是一项很好的锻炼。或者只是手工完成

问这个问题的另一种方法是,我们能否创建一个由 1 和 0 组成的对称矩阵,其行的值相等。这将是“谁扮演谁”的表格。把它想象成一个 N×N 网格,其中 grid[i][j] = grid[j][i] (如果你扮演某人,他们扮演你)和 grid[i][i] = 0 (没有人扮演自己)

例如

Input: 4 3 3 3 3 Output: 1

好像

 0 1 1 1
 1 0 1 1
 1 1 0 1
 1 1 1 0 

但是,我们不能用这个来做到这一点:输入:3 2 2 0 输出:0

编辑

这相当于这个(来自度(图论)

Hakimi (1962) 证明(d1, d2, ..., dn)是简单图的度数序列当且仅当(d2 − 1, d3 − 1, ..., dd1+1 − 1, dd1+ 2, dd1+3, ..., dn)是。这一事实导致了一种简单的算法,用于找到具有给定可实现度数序列的简单图:

  1. 从没有边的图开始。
  2. 按照剩余度要求的非递增顺序维护其度要求尚未满足的顶点列表。
  3. 将第一个顶点连接到此列表中的下一个d1顶点,然后将其从列表中删除。重新排序列表并重复,直到满足所有学位要求。

查找或估计具有给定度数序列的图数的问题是图枚举领域的问题。

于 2012-04-25T20:50:11.017 回答
2

也许您可以获取运动员的比赛数量数组,并确定其中的最大数量。

然后看看您是否可以将该数字拆分为 1,并从数组的其他几个成员中减去这些 1。

将最大数量的数组成员清零,并将其从数组中删除,并使用减少的值更新其他成员。

现在,重复这个过程——确定新的最大数,然后从数组的其他成员中减去它。

如果在任何时候没有足够的数组成员从中减去 1,则让应用程序返回 0。否则继续执行此操作,直到数组中没有更多成员,此时您可以让应用程序返回 1。

此外,请记住删除减少到零的数组成员。

于 2012-04-25T20:54:30.017 回答
0

编辑:下面的解决方案将一些无效输入传递为有效。这是检查明确否定的快速方法,但它允许误报。


以下是数学家的建议:

  1. 匹配数的总和必须是偶数。3 3 4 2 1总和为13,这意味着有人与自己进行了一场比赛。
  2. 对于n球员来说,如果每场比赛都淘汰了一名球员,则至少n-1必须进行不同的比赛。(淘汰赛。)要查看这一点,请为 2、4、8、16、32... 名玩家绘制比赛树,需要 1、3、7、31... 场比赛来决定获胜者。
  3. 对于n玩家来说,如果每个人都玩一次,假设没有重复比赛,则最大比赛次数是n choose 2,或(n!)/(2!)(n-2)!(循环赛)。n!是阶乘函数,n! = n * n-1 * n-2 * ... * 3 * 2 * 1.

所以标准是:

  1. 匹配数的总和必须是偶数。
  2. 匹配数的总和必须至少为2n-2。(注意乘以 2 - 每场比赛都会导致双方玩家的计数都增加 1。)
  3. 匹配数的总和最多为2 * n choose 2
  4. [编辑] 每个玩家必须至少参加一场比赛。

如果您的比赛是淘汰赛和循环赛之间的交叉,您可能会有介于n-1n choose 2比赛之间的地方。

编辑:

如果任何球员的比赛超过了n-1比赛,他们至少与某人比赛了两次。

如果您的锦标赛是淘汰赛,以便每个玩家参加尽可能少的比赛,那么每个玩家最多可以参加大约2log_2(n)场比赛(以log2 为基础并向上取整。)在 16 名玩家的锦标赛中,最多 4火柴。在 1024 名玩家的比赛中,最多 10 场比赛。

于 2012-04-25T20:57:17.920 回答
0

您的示例都可以通过计算匹配项并查看它们是否除以 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 名玩家,他们每人的比赛不能超过 2 场。

于 2012-04-25T21:42:53.620 回答