OI普及组周赛18题解 -C

C

发现我们可以先在这个地宫中使用把所有可以到达的格子搜索出来,并且在搜索的过程中找到所有能够使用的宝藏并记录下他们的能力值.然后我们把这些宝藏的能力值当成一个序列,发现我们要求这个能力值之差最小,如果我们要枚举能力值区间的左端点的话.那么我们把某个宝藏的能力值当成这个能力值区间的左端点一定会比枚举其他的值当作左端点会更优.而且这个右端点也一定是落在某个宝藏的能力值上最优.而对于这个能力值区间,我们关心的是它是否包含了个不同的能力值,如果我们把每个能力值当成一个点的话,我们要求的就是让这个区间包含个点并且这个区间的长度最长.

但是这样的话我们会遇到一个问题:有很多的权值没有出现过,而且权值的范围太大,不允许我们直接枚举.

所以我们就要将出现过的这些权值离散化,根据我们之前的结论,我们可以在离散化之后将序列去重,然后我们使用双指针的方法,枚举每个左端点,然后右端点可以通过计算计算出来,然后统计一下现在的权值之差,取一个最小值即为答案.