Peu importe que ce soit dans l'ordre croissant ou dans l'ordre décroissant, vérifiez simplement si vous pouvez les empiler un par un.
from heapq import heappush, heapreplace
N, *A = map(int, open(0).read().split())
A.sort()
q = [A[0]]
for a in A[1:]:
if a <= q[0] + 1:
heappush(q, a)
else:
heapreplace(q, a)
print(len(q))
Rebondir une fois x, rebondir une fois 3/2 * x, rebondir deux fois 7/4 * x, rebondir 3 fois 15/8 * x, rebondir n fois (2 n + 1) </ sup> -1) / 2 n </ sup> * x. D ≤ 10 18 </ sup>, donc si vous rebondissez 60 fois, la distance de vol n'augmentera pas après cela. Vous devriez vérifier s'il y a une réponse lorsque vous rebondissez 60 fois, 59 fois, ..., une fois. Puisqu'il y a un effet de troncature, j'ai vérifié environ ± 100 avant et après convenablement et AC.
D = int(input())
def f(x):
result = 0
while x != 0:
result += x
x //= 2
if result >= D:
break
return result
for i in range(60, 0, -1):
t = D * (2 ** (i - 1)) // (2 ** i - 1)
for j in range(-100, 100):
if t + j < 0:
continue
if f(t + j) == D:
print(t + j)
exit()
Recommended Posts