思路

考虑预处理出连续区间，我们只能使用至多一次翻倍操作。

这里的连续区间是指，这个区间内的数从小到大排序后，相邻元素的差至多为 2。

考虑每两个相邻的连续区间是否可以连在一块，如果可以则更新答案。

注意一个边界情况：区间 [3, 5] 和 [7, 100]

如果将 [3, 5] 的 3 翻倍为 6 ，那么可以得到 [4, 5], [6], [7, 100]，形成一个 [4, 100] 的连续区间。

然后二分答案即区间长度，每次 check 枚举左端点，然后计算得到右端点

预处理出前缀和，然后计算当前区间 $[l, r]$ 中出现过的数的数量。

• 如果正好为区间长度，则 OK
• 如果正好为区间长度减 1，找到那个唯一未出现的数 p ，判断是否可以通过乘 2 操作获得这个数
  • 如果当前 p >= l，查看当前 cnt[l] > 1 是否成立
  • 如果当前 p < l ，那么需要判断这个 p 之前是否出现过，这部分可以二分($O(\log n)$)也可以用哈希表($O(1)$)

时间复杂度：$O(n\log n\log n)$

二分为 $O(\log n)$ ，check 函数为 $O(n\log n)$ ，瓶颈在于需要二分找到小于 l 的 p 是否存在

代码

import bisect

def find_p(x, b):
    idx = bisect.bisect_left(b, x)
    return idx < len(b) and b[idx] == x

def check(mid, maxc, start, pre, next_zero, cnt, find_p):
    for l in range(1, maxc - mid + 3):
        r = l + mid - 1
        if pre[r] - pre[l - 1] == mid:
            return True
        elif mid - (pre[r] - pre[l - 1]) == 1:
            p = start + next_zero[l] - 1
            if p % 2 != 0:
                continue
            p //= 2
            if p < l + start - 1:
                if find_p(p):
                    return True
            elif cnt[l] > 1:
                return True
    return False

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    b = list(set(a))
    b.sort()

    m = n * 4
    cnt = [0] * m
    pre = [0] * m
    next_zero = [0] * m

    ans = 0
    i = 0
    while i < n:
        j = i + 1
        while j < n and a[j] - a[j - 1] <= 2:
            j += 1

        minv = a[i]
        maxv = a[j - 1]
        length = maxv - minv + 1
        last = length * 2
        cnt = [0] * (last + 1)
        pre = [0] * (last + 1)
        next_zero = [length + 1] * (last + 1)

        for k in range(i, j):
            idx = a[k] - minv + 1
            cnt[idx] += 1
            pre[idx] = 1

        for k in range(1, last + 1):
            pre[k] += pre[k - 1]

        for k in range(last, 0, -1):
            if cnt[k] == 0:
                next_zero[k] = k
            else:
                next_zero[k] = next_zero[k + 1]

        l = 1
        r = length + 1
        while l < r:
            mid = (l + r + 1) // 2
            if check(mid, length, minv, pre, next_zero, cnt, lambda x: find_p(x, b)):
                l = mid
            else:
                r = mid - 1

        ans = max(ans, l)
        i = j

    print(ans)


if __name__ == "__main__":
    main()

题目描述

小红有$n$颗糖果，每颗糖果的编号为$a_i$。小红给自己定下的目标是，第$x$天必须吃编号为$x$的糖果。现在小红有一个魔法，可以选择一颗糖果，将其编号翻倍。小红最多只能释放一次魔法。她希望自己连续尽可能多的天数都能吃到糖果，请你求出最多的连续天数。

输入描述

第一行输入一个正整数$n$，代表糖果数量。 第二行输入$n$个正整数$a_i$，代表每个糖果的编号。

$1\le n\le 10^5$

$1\le a_i\le 10^9$

输出描述

一个正整数，代表最多能吃到糖果的连续天数。

样例1

输入

4
1 1 3 5

输出

3

说明

选择第一个糖果，将其编号变成 2，那么第 1、2、3 天都能吃到糖果，最多连续3天。

样例2

输入

5
4 2 5 3 6

输出

5

说明

不需要使用魔法，从第 2 天到第 6天都可以吃到糖果。