有N个节点（1长的一维长度。第i个节点在位置x_i（an
范围为0…100000000的整数，并且具有节点类型B_I（中的整数
范围1..8）。节点不能在同一位置
您需要在这个一维上获得一个范围，其中所有类型的节点都在其中得到公平的表示。因此，您要确保对于范围中存在的任何类型的节点，每种节点类型的数量相等（例如，类型1和3中的每种类型有27个的范围是可以的，类型1、3和4中的每种类型有27个的范围是可以的
好，但1型的9和3型的10不好）你也想要
要在
兰特找到满足约束条件的最大范围。照片的大小是照片中节点的最大和最小位置之间的差异。
如果没有满足约束的范围，则输出-1。
INPUT:
* Line 1: N and K separated by a space
* Lines 2..N+1: Each line contains a description of a node as two
integers separated by a space; x(i) and its node type.
INPUT:
9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3
INPUT DETAILS:
Node types: 1 2 3 - 1 1 2 3 1 - ... - 1
Locations: 1 2 3 4 5 6 7 8 9 10 ... 99 100
OUTPUT:
* Line 1: A single integer indicating the maximum size of a fair
range. If no such range exists, output -1.
OUTPUT:
6
OUTPUT DETAILS:
The range from x = 2 to x = 8 has 2 each of types 1, 2, and 3. The range
from x = 9 to x = 100 has 2 of type 1, but this is invalid because K = 2
and so you need at least 2 distinct types of nodes.
你能帮忙提出一些算法来解决这个问题吗？我考虑过使用某种优先级队列或堆栈数据结构，但真的不确定如何继续。
谢谢，托德
最佳答案
发明几乎线性时间算法并不太困难，因为最近在CodeChef:"ABC-Strings"上讨论了类似的问题。
根据节点的位置对其排序。
准备所有可能的节点类型子集（例如，我们可以期望类型1、2、4、5、7出现在结果间隔中，而所有其他类型不出现在结果间隔中）。对于k=2，可能只有256-8-1=247个子集。对于每个子集，执行其余步骤：
将8个类型计数器初始化为[0,0,0,0,0,0,0,0]。
对于每个节点，执行其余步骤：
当前节点类型的增量计数器。
取包含到当前子集的类型的L计数器，从其他L-1计数器中减去其中的第一个，这将产生L-1值取剩余的8-L计数器，并将它们与那些L-1值组合成7个值的元组。
将此元组用作哈希映射的键。如果哈希映射不包含该键的值，则添加一个新项，该项的值等于当前节点的位置。否则，从当前节点的位置减去哈希映射中的值，并（可能）更新最佳结果。
关于algorithm - 确定最长的连续子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22901287/