不使用结构冒泡某种条件？_java

有比赛。 玩家通过整数进行ID识别，并以与他们相邻的整数的锦标赛风格进行比赛。 因此，1场，2场，4场，5场，6场，7场8。然后，1/2场3 / 4、5 / 6场7/8，然后1/2/3/4场5/6 / 7/8。

输入样例：

8 5
1 2 3 4 5

第一行=第一个数字是锦标赛中的玩家人数（总是2 ^ N个数字），第二个数字是锦标赛开始前退出的玩家数

第二行=退出玩家的ID

如果一个玩家因为要玩的人退出而自动前进到下一轮（称其为BYE），则增加一个计数。 最后输出计数。

因此，样本输入的输出将为2（在第一轮中自动前进6，因为本来应该有6参加了5个退出的比赛，最终在倒数第二轮中6/7/8自动前进）。

我正在考虑要么将所有内容都保存在一棵树上（但这真的不是很有效吗？），或者只是随便进行解析，然后冒充BYE。 第二种解决方案的问题是，我不知道如何根据谁将扮演谁来考虑/存储关系，以及在实施过程中您如何准确地在没有结构的情况下冒犯某些东西。

您可以使用一个简单的数组（大小为2 ^ N）逃脱。 将您的参与者编码为0（缺席）和1（当前），并模拟比赛。 在每个回合中，索引为2*k玩家再次下注索引2*k + 1 ，“赢家”移至索引k 。 再见条件是XOR，“获胜者”是OR。 用伪代码，

    while player_count > 1
        for k in range (player_count / 2)
            byes += arr[2*k] ^ arr[2*k + 1]
            arr[k] = arr[2*k] | arr[2*k + 1]
        player_count /= 2

玩家人数的空间和时间都是线性的。

没有结构，您将无法存储任何内容，但是某些时间结构可能是隐式的，例如，在递归的情况下，我们有未明确声明的堆栈。

下面是递归解决方案的示例：

public class App {
    public static void main(String[] args) {
        // I use 0 based indexing here
        Set<Integer> absent = new HashSet<>(Arrays.asList(0, 1, 2, 3, 4));

        int count = rec(absent, 8, 0);
        System.out.println("count = " + count);
    }

    private static int rec(Set<Integer> absent, int currentGroupSize, int start) {
        if (currentGroupSize == 1) {
            return absent.contains(start) ? -1 : 0;
        }

        int r1 = rec(absent, currentGroupSize / 2, start);
        int r2 = rec(absent, currentGroupSize / 2, start + currentGroupSize / 2);
        if (r1 == -1) {
            if (r2 == -1) {
                return -1;
            } else {
                return r2 + 1;
            }
        } else {
            if (r2 == -1) {
                return r1 + 1;
            } else {
                return r1 + r2;
            }
        }
    }
}

这是时间O(R log R)和空间O(R) ，其中R是退休（退出）玩家的数量。 如果按ID的升序分配退休球员，则您的最后见解是正确的：您可以读取ID并将其冒充到O(R)时间和O(1)内存中。 当N远大于R （例如，数十亿）时，这会有所帮助，因为这会阻止存储任何大小为N数组。

从概念上讲，退休的玩家ID是一棵树上的叶子。 这是N = 8的树。我从所有ID中减去1，因为事实证明这是一个有点黑客的问题，并且有些黑客喜欢从0开始计数。:-)

           0-7
        /       \
     0-3         4-7
   /     \     /     \
 0-1    2-3   4-5    6-7
 / \    / \   / \    / \
0   1  2   3 4   5  6   7

想法是查看输入中的紧凑范围，并找出它们产生了多少个再见。 例如，范围[0-3]产生一个再见：左括号（子树）中不玩游戏，并且从范围[4-7]进入决赛的人进入决赛。 范围[4-7]也是如此。 基本上，如果一个范围覆盖一整个子树，那就是再见。 请注意，我们分别寻找最大的完整子树，例如[0-3]，而不是[0-1] + [2-3]。

那[0-4]呢？ 我们需要将范围分为[0-3]和[4-4]。 然后[4-4]是第二个子树（一个只有一个节点的琐碎的子树），这意味着玩家5也将获得再见。 因此[0-4]算作两个再见。 我们通过对数字5（范围的大小）中的位数进行计数来确定这一点。 由于5 = 101 ₂ ，我们得到答案2。这是一点技巧，我将对此进行介绍，但可以根据需要进行扩展。

最后要考虑的问题是限制范围大小。 令N=1024并考虑范围[4-100]。 从4开始，子树将填充到7，这时我们应该处理范围[4-7]（并获得1再见），然后从8开始继续（子树将依次填充到15，依此类推）。 计算正确的端点还涉及一些破解。 考虑起点40 = 101000 ₂ 。 子树的大小由最低有效位给定，即1000 ₂ = 8，因此我们应该在范围[40-47]之后中断。 同样，我将详细介绍细节，但如果需要可以扩展。

事实证明，C代码很短（很久以前不写Java的道歉）。 为简便起见，它使用GCC 对位进行计数，但是还有可用。 同样，限制范围大小涉及。

#include <stdio.h>

void startRange(unsigned p, unsigned* start, unsigned* end, unsigned* limit) {
  *start = *end = p;
  *limit = p + (p & -p) - 1;
  printf("started range %u limit %u\n", p, *limit);
}

int processRange(unsigned start, unsigned end) {
  printf("processing range [%u,%u]\n", start, end);
  return __builtin_popcount(end - start + 1);
}

int main() {
  unsigned n, r, p, result;
  unsigned start, end, limit;

  /* read from standard input */
  scanf("%d%d%d", &n, &r, &p);
  startRange(p - 1, &start, &end, &limit);
  result = 0;

  while (--r) { /* read r-1 more numbers */
    scanf("%d", &p);
    p--;

    if (p == end + 1 && p <= limit) {
      /* continue while we have consecutive numbers, but not past the limit */
      end++;
    } else {
      /* close the previous range and start a new one at p */
      result += processRange(start, end);
      startRange(p, &start, &end, &limit);
    }
  }

  /* close any outstanding range we have */
  result += processRange(start, end);
  printf("%d\n", result);

  return 0;
}

不使用结构冒泡某种条件？

问题描述

1楼

2楼

3楼