题目大意
一个序列删除一个最小的区间,使得剩下的数俩俩各不相同。
解题思路
对于前60%60\%60%的数据,可以直接暴力 O(n2)O(n^2)O(n2) 枚举。枚举每次删除的长度 LenLenLen 然后剩下的数再扫一边,判断有没有重复就可以获取答案。
100%100\%100%数据的解法用二分答案的思想,二分答案然后用 O(n)O(n)O(n) 的时间确定一下答案是否合法就可以。怎么用 O(n)O(n)O(n) 时间判断呢。注意到,重复的意思就是出现两次以上,那么只有在出现一次和出现二次之间变化的时候才会影响答案的统计。那么统计一下每个数的出现次数,在扫答案的时候维护就可以了。可以用 unordered_mapunordered\_mapunordered_map 或者 离散化处理 1e9 的数据(详细看代码就可以了)
参考代码
(unordered_map)
离散化