AtCoder Beginner Contest C - Tsundoku Difficulty: 878
Ce thème, somme cumulée + dichotomie
Au début, je pensais que c'était une méthode de planification dynamique, mais j'ai eu «TLE» ~~ une grosse perte de temps ~~, et je suis passé à une dichotomie. Dans l'exemple d'entrée 1, dans chaque ligne du tableau suivant, recherchez le nombre maximal de bureaux A et B qui ne dépassent pas K minutes.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 60 | 90 | 120 | 80 | 150 | 80 | 150 |
| 60 | 90 | 80 | 150 | 80 | 150 | |
| 60 | 80 | 150 | 80 | 150 | ||
| 80 | 150 | 80 | 150 |
Ruby
ruby.rb
n, m, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = Array.new(n + 1, 0)
n.times do |i|
c[i + 1] = c[i] + a[i]
end
d = Array.new(m + 1, 0)
m.times do |i|
d[i + 1] = d[i] + b[i]
end
cnt = 0
0.upto(n) do |i|
break if c[i] > k
e = d.bsearch_index{_1 > k - c[i]}
if e.nil?
cnt = i + m if cnt < i + m
else
cnt = i + e - 1 if cnt < i + e - 1
end
end
puts cnt
ruby.rb
c = Array.new(n + 1, 0)
n.times do |i|
c[i + 1] = c[i] + a[i]
end
d = Array.new(m + 1, 0)
m.times do |i|
d[i + 1] = d[i] + b[i]
end
Somme cumulée.
ruby.rb
e = d.bsearch_index{_1 > k - c[i]}
if e.nil?
cnt = i + m if cnt < i + m
else
cnt = i + e - 1 if cnt < i + e - 1
end
C'est une dichotomie. Si la valeur maximale du tableau est dépassée, «nil» est renvoyé, de sorte que le processus est inclus. Python
python.py
from sys import stdin
import bisect
def main():
input = stdin.readline
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * (n + 1)
for i in range(n):
c[i + 1] = c[i] + a[i]
d = [0] * (m + 1)
for i in range(m):
d[i + 1] = d[i] + b[i]
cnt = 0
for i in range(n + 1):
if c[i] > k:
break
e = bisect.bisect_right(d, k - c[i])
if cnt < i + e - 1:
cnt = i + e - 1
print(cnt)
main()
python.py
e = bisect.bisect_right(d, k - c[i])
if cnt < i + e - 1:
cnt = i + e - 1
C'est une dichotomie. Si la valeur maximale du tableau est dépassée, le «numéro d'élément + 1» du tableau est renvoyé.
| Ruby | Python | |
|---|---|---|
| Longueur du code(Byte) | 433 | 570 |
| Temps d'exécution(ms) | 349 | 246 |
| Mémoire(KB) | 44860 | 47636 |
Site référencé
Recommended Posts