您的排名纯粹是 Google Code Jam 协助

问题描述 投票:0回答:1

我已经被这个问题困扰了一段时间(https://code.google.com/codejam/contest/635101/dashboard#s=p2)。

在问题的分析中(https://code.google.com/codejam/contest/635101/dashboard#s=a&a=2)我明白K是集合S中N的排名,它将始终是最大和结束的数字。

然而,它说“假设S'中有K'个数字”。但既然K是数的秩,那岂不是和K'一样了?

S' 的数字数量似乎与 S 不同?是这样吗?

algorithm math rank
1个回答
1
投票

S' 定义为 S 与 {1, 2, ..., K} 的交集。现在,即使 S' 本身看起来好像是 {1, 2, ..., K},但事实可能并非如此。

您应该选择 S 作为集合 {2, 3, ..., N} 的子集。它不必由集合 {2, 3, ..., N} 中的“全部”元素组成。考虑到这一点时,S 与 {1, 2, ..., K} 的交集不必包含所有元素 {1, 2, ..., K}。因此,当教程说“假设 S' 中有 K' 个数字”时,K 不一定是 K',因为 S' 的数字数量与 S 不同。 考虑到 S' 的定义,可以直观地注意到 S' 与 S 的元素数量不同。 S 是 {2, 3, ..., N} 的子集,而 S' 是 S 与 {1, 2, ..., K} 的交集。

© www.soinside.com 2019 - 2024. All rights reserved.