AtCoder Beginner Contest C - Tsundoku Difficulty: 878
Dieses Thema, kumulative Summe + Dichotomie
Zuerst dachte ich, es sei eine dynamische Planungsmethode, aber ich bekam TLE ~~ einen großen Zeitverlust ~~ und wechselte zu einer zweiminütigen Suche.
In Eingabebeispiel 1 finden Sie in jeder Zeile der folgenden Tabelle die maximale Anzahl von Schreibtischen A und B, die K Minuten nicht überschreiten.
| 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
Kumulative Summe.
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
Es ist eine Zweiteilung. Wenn der Maximalwert des Arrays überschritten wird, wird "nil" zurückgegeben, sodass dieser Prozess eingeschlossen wird. 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
Es ist eine Zweiteilung. Wenn der Maximalwert des Arrays überschritten wird, wird die "Elementnummer + 1" des Arrays zurückgegeben.
| Ruby | Python | |
|---|---|---|
| Codelänge(Byte) | 433 | 570 |
| Ausführungszeit(ms) | 349 | 246 |
| Erinnerung(KB) | 44860 | 47636 |
Referenzierte Site
Recommended Posts