Es spielt keine Rolle, ob es in aufsteigender oder absteigender Reihenfolge ist. Sie müssen also nur prüfen, ob Sie sie einzeln stapeln können.
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))
Einmal springen x, einmal springen 3/2 * x, zweimal springen 7/4 * x, 3 mal springen 15/8 * x, n-mal springen (2 n + 1) </ sup> -1) / 2 n </ sup> * x. D ≤ 10 18 </ sup> Wenn Sie also 60 Mal springen, erhöht sich die Flugentfernung danach nicht mehr. Sie sollten überprüfen, ob es eine Antwort gibt, wenn Sie 60-mal, 59-mal, ..., einmal springen. Da es einen Abschneideeffekt gibt, habe ich vor und nach dem Anpassen ungefähr ± 100 und AC überprüft.
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