我如何使用结构数组解决此问题？ [处于保留状态]

Question

我对这类问题还很陌生，我想知道我的方法应该是什么。我已经为这个问题抓了几个小时，详细的答案将不胜感激。

种族条件

您正在为N个孩子（编号从1到N）进行无休止的比赛，这要求他们跑到场地的另一端并无限地返回。在比赛的一端，比赛开始，在另一端，是一个装有无限数量的K色（编号从1到K）的球的袋子。每种K颜色的球数量相等。他们的目标是跑到球场的另一端，从袋子中随机捡起一个球，然后跑回你身边，再给你球，从而尽可能多地收集球。他们一次不能接球或给你一个以上的球。由于这是一场无休止的比赛，他们注定要永远这样做。您可以负责，在任何时候，您都可以根据以下条件生成排名列表：

1. 收集了更多球的孩子排名更高比一个球数少的人。
2. [如果两个孩子的球数相同，我们会安排他们以颜色ID的非降序收集的球并放置具有更多ID较低的球的那个更高。
3. [如果两个孩子的球数相同，并且球数相同在每种颜色的比赛中，第一个将球绑在得分更高。
4. 比赛最初是按照孩子们的升序排列的他们的ID，每个都有0个球。

输入格式

输入的第一行是N和K。

第二行包含Q，即查询数量。 Q行。

查询有两种类型：

类型1：1 x y

这意味着ID为x的孩子在那一秒钟给您ID为y的球。

类型2：2 z

这意味着您必须在排名列表中产生直到该秒的第z个孩子。

约束

1

1

1

输出格式

仅对于类型2查询，才需要输出。在这种情况下，仅将一个整数打印到新行上，这是排名列表中第z个孩子的ID。

样本输入0

3 3
5
1 1 3
1 2 2
2 1
1 1 2
2 1

样本输出0

2
1

样本输入1

3 3
10
1 1 3
1 1 1
1 2 2
2 2
1 3 2
1 3 1
1 1 3
2 1
2 2
2 3

样本输出1

2
1
3
2

Answer 1

这是使用结构数组的一种方法。

您的结构必须包含有关每个孩子的相关信息。特别是他收集的每种类型的球的数量。可能您也希望保留总数，这样您就不必不断地对它们求和。看来您还需要跟踪孩子最后一次给您发球的时间。而且，当然，您想保留总分。

您有N个孩子组成的数组。一个孩子的数字（0到N-1）对应于他在数组中的位置（0到N-1）。通过对数组进行索引并更新该孩子的结构，可以轻松解决查询＃1的问题。

对于＃2，您可以使用Quickselect查找得分最高的孩子。

对于类型1的查询该设置为O（1），对于类型2的查询设置为O（n）。

您可以进行一些优化来改善这一点，但这是简单的版本。