网球锦标赛算法

Question

在网球锦标赛之后,每个球员被问到他有多少场比赛.运动员不能与另一名运动员进行多场比赛.作为输入,你唯一拥有的是运动员的数量和每个运动员的比赛.作为输出,如果比赛可以根据运动员的答案进行,你将获得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);
    }
}

我不想要一个简单的解决方案,也许只是一些提示和提示,因为我们真的不知道还有什么要做,我重复,即使我将它标记为作业(因为我觉得版主将再次关闭它)它不是,这只是我兄弟找到的东西,我们正在努力解决.

很多人都回答了,我真的很感激,但是因为我明天有工作需要去睡觉,所以我明天可能会阅读其余的答案,看看有什么用

Answer 1

不确定它是否100%工作,我会像:

1. 排序输入

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

   • 基于索引i处的元素的值n,将左元素减少1
   • 如果由于您到达列表末尾或值0而无法减少,则返回失败

3. 回归成功.

这个逻辑(如果正确的话)可能导致对O(N*log(N))解决方案的一些修改,但我目前认为这对新手程序员来说太过分了.

编辑:

这在输入
2 2 1 1 上无法正常工作

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

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

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

2. 好的

Answer 2

这是一个提示.回答这些问题

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

编辑

这相当于此(来自Degree(图论))

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

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

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