AtCoder Beginner Contest D - Enough Array Difficulty: 859
Dieses Thema, kumulative Summe + Dichotomie
Problemstellung (Bedingung) Die Summe der Werte aller in der fortlaufenden Unterspalte enthaltenen Elemente ist K oder mehr. Aus können Sie sehen, dass die kumulative Summe verwendet wird, aber da 1 ≤ N ≤ 100_000 ist, wird die Schleife, wenn Sie sie zweimal drehen, zu TLE.
Da die kumulative Summe eine monotone Zunahme ist, wird daher auch eine Dichotomie verwendet, um den Rechenaufwand zu verringern.
Ruby
ruby.rb
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
acc = 0
x = [0] + a.map{|v| acc += v}
cnt = 0
x.each do |y|
j = x.bsearch_index{|z| z - y >= k}
if j == nil
break
else
cnt += n - j + 1
end
end
puts cnt
accumulate.rb
acc = 0
x = [0] + a.map{|v| acc += v}
Die kumulative Summe wird hier berechnet. ** Nachtrag ** Ich habe es an den Code angepasst, den Sie in den Kommentaren erhalten haben.
bsearch.rb
j = x.bsearch_index{|z| z - y >= k}
Obwohl es sich um eine Dichotomie handelt, wird "lower_bound" in *** C ++ *** zu "bsearch" oder "bsearch_index" in *** Ruby ***. Python
python.py
from sys import stdin
def main():
import bisect
import itertools
input = stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
x = [0] + list(itertools.accumulate(a))
cnt = 0
for z in x:
j = bisect.bisect_left(x, k + z)
if j <= n:
cnt += n - j + 1
print(cnt)
main()
accumulate.py
x = [0] + list(itertools.accumulate(a))
*** Python *** hat eine Funktion namens "akkumulieren", die die kumulative Summe berechnet.
bisect.py
j = bisect.bisect_left(x, k + z)
Es ist eine Dichotomie, aber verwenden Sie "bisect" oder "bisect_left", "bisect_right".
Wenn sich die zu suchende Zahl im Array befindet, gibt bisect die Position rechts von dieser Zahl zurück und bisect_left gibt die Position links zurück.
for.py
for z in x:
for i in range(n):
Als ich die Schleife mit "range ()" drehte, war es "TLE".
| Ruby | Python | |
|---|---|---|
| Codelänge(Byte) | 238 | 377 |
| Ausführungszeit(ms) | 165 | 101 |
| Erinnerung(KB) | 11780 | 14196 |
Referenzierte Site
Recommended Posts